10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

I think that this is in fact not possible, thanks to the (recent and difficult!) ICALP'22 results of Göös et al.. They show that there are UFAs $A_1$ and $A_2$ with $n$ states such that the language $...
a3nm's user avatar
  • 9,232
7 votes
Accepted

The complexity of conversion from a regular expression to a nondeterminsitic automata and back after changing initial and final states

As observed in the proof of Theorem 6 (later dubbed the "Star Height Lemma") of Gruber/Holzer ICALP 2008, when converting a regular expression into an $\varepsilon$-NFA, then the underlying ...
Hermann Gruber's user avatar
4 votes
Accepted

Complexity of the inevitability problem over monoids

I think it is PSpace-complete, here is a proof scheme. We can go back to the proof scheme for PSpace-completeness of regular expression universality, e.g. described in this answer. There we can see ...
Denis's user avatar
  • 8,678
4 votes

Logical Equivalents of Finite State Transducers

By a transducer I assume you mean an automaton which can print output on transitions. The extensional equivalence between deterministic and nondeterministic automata as well as 1-way and 2-way ...
Siddharth's user avatar
  • 823
4 votes
Accepted

Defining regular language classes with disjoint union

Interesting, I was recently writing a blog post on a related topic. Namely, you have probably seen the term rational languages used for regular languages. This is because the generating function (g.f.)...
GBathie's user avatar
  • 296
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
3 votes
Accepted

What is the solution of this equation on regular languages?

$L$ is regular. I'll prove this for $n=1$; then it follows for arbitrary $n$, as the intersection of regular languages is itself regular. Define $$L = \{x \in \Sigma^* \mid \{x\} \cdot A \subseteq B\}...
D.W.'s user avatar
  • 12k
3 votes

Defining regular language classes with disjoint union

This question has indeed been studied: namely, from the perspective of representing regular languages as unions of so-called regular components that is, loop expressions of the form $uv^+w$, and a ...
Hermann Gruber's user avatar
2 votes
Accepted

What is the current state of the art on exact identification of DFAs with a maximum N states

The last step of the proposed reasoning can be done as described in https://cs.stackexchange.com/questions/48136/testing-two-dfas-generate-the-same-language-by-trying-all-strings-upto-a-certain and in ...
EXPTIME-complete's user avatar
2 votes
Accepted

Are regular expressions polynomially decomposable?

The answer to my question turned out to be positive, which follows from a translation from regular expressions to automata and back. Check the answer of Hermann Gruber to my previous POST.
Bartosz Bednarczyk's user avatar
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
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
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
1 vote

What is the intution on the TTT algorithm for regular grammar inference?

If you get a counterexample back from the teacher the counterexample is very long. If the suffix analysis is used as described in the paper, the suffix can be very long, this suffix is added in the ...
Coping Forever's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible