New answers tagged

2 votes

Obscure characterizations of the regular languages

Here are fun ones: computational interpretations of circular proofs for Kleene algebra in linear logic, see https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.45 (Theorem 24) ...
Denis's user avatar
  • 8,678
2 votes

Obscure characterizations of the regular languages

I think this one may fit the bill: A language is regular if and only if its characteristic series is the support of an $\mathbb{N}$-rational series. Definitions. Let $\Sigma$ be an alphabet and $\...
Ekene E.'s user avatar
  • 121
2 votes

Obscure characterizations of the regular languages

A language is regular if and only if it is linearly separable by the DFA kernel, defined here: How many DFAs accept two given strings? This is Theorem 11 in https://www.sciencedirect.com/science/...
Aryeh's user avatar
  • 10.5k
3 votes

Is there a simple characterization of regular languages closed under circular shifts?

We can propose an automaton model characterizing regular circular languages: a C-automaton is an NFA where all states are initial. A run must see an accepting state somewhere, and must start and end ...
Denis's user avatar
  • 8,678
2 votes

Is it useful to "untangle" an NFA by converting to a regular expression and back

In fact, this roundtrip conversion is used in the proof of the Star Height Lemma, and this in turn has lots of implications in the area of descriptional complexity of regular expressions. And here it ...
Hermann Gruber's user avatar
2 votes

Is there a simple characterization of regular languages closed under circular shifts?

Just an extended note trying to recover my previous (wrong) answer. A language $L$ is closed under cyclic shifts if and only if $aw \in L \Leftrightarrow wa \in L\;$ ($a \in \Sigma$) indeed after ...
Marzio De Biasi's user avatar

Top 50 recent answers are included