20 votes

Automata learning without counterexamples

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need ...
Aryeh's user avatar
  • 10.3k
17 votes
Accepted

Regular versus TC0

Take $S_5$ as alphabet and $$L= \{ \sigma_1\cdots \sigma_n \in S_5^*\mid \sigma_1\circ\cdots\circ\sigma_n = \text{Id}\}$$ Barrington proved in [2] that $L$ is $\textrm{NC}^1$-complete for $\textrm{AC}...
C.P.'s user avatar
  • 992
16 votes

Hierarchies in regular languages

Here is a list of several hierarchies of interest, some of which were already mentioned in other answers. Concatenation hierarchies A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if $...
J.-E. Pin's user avatar
  • 4,771
15 votes

Regular versus TC0

Regular languages with unsolvable syntactic monoids are $\mathrm{NC}^1$-complete (due to Barrington; this is the underlying reason behind the more commonly quoted result that $\mathrm{NC}^1$ equals ...
Emil Jeřábek's user avatar
15 votes
Accepted

Parameterized complexity of inclusion of regular languages

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even ...
Denis's user avatar
  • 8,598
13 votes

On the realisation of monoids as syntactic monoids of languages

The terminology rigid seems to be relatively new compared to the term disjunctive used in the late 70's (and probably before, I didn't check for earlier references). A subset $P$ of a monoid $M$ is ...
J.-E. Pin's user avatar
  • 4,771
12 votes
Accepted

On the realisation of monoids as syntactic monoids of languages

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without ...
Denis's user avatar
  • 8,598
12 votes

Hierarchies in regular languages

Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA. We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$ ($D = \{...
Marzio De Biasi's user avatar
11 votes

On the realisation of monoids as syntactic monoids of languages

In a more elementary way than Denis's answer, the following is extracted from Pippenger's "Theories of Computability", p.87, and immediate to check. Definition: Let $M$ be a monoid, and $Y \subseteq ...
Michaël Cadilhac's user avatar
11 votes

Existence of an algorithm

A language $L$ is said to be commutative if the following property holds: for every word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm ...
J.-E. Pin's user avatar
  • 4,771
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
  • 8,896
9 votes

Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...
Miklós István's user avatar
9 votes

In the context of regular languages, must the alphabet be finite?

It makes sense in some contexts in mathematics to consider strings or languages over infinite alphabets. For instance, this concept is used in the strong version of Higman's lemma. But a finite ...
David Eppstein's user avatar
9 votes

Transition monoid membership for DFAs

Decidability It's decidable. There are only finitely many possible functions $f:Q \to Q$, so you can model this as a graph reachability problem, with one vertex per function and an edge $g \to h$ if ...
D.W.'s user avatar
  • 11.7k
9 votes
Accepted

Finding a minimal DFA whose language has a desired intersection with another

$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$. Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ ...
Dmitri Urbanowicz's user avatar
9 votes

Planarity of planar finite automata intersection

As mentioned in my comment, the usual product construction does not preserve planarity. In fact, there is an intersection of regular languages that can be described by a nonplanar NFA with $n$ states, ...
Hermann Gruber's user avatar
8 votes

In the context of regular languages, must the alphabet be finite?

The usual convention in formal languages and automata theory is that an alphabet is finite. However, there are certainly some cases where it's useful to think of an alphabet being infinite. For ...
Jeffrey Shallit's user avatar
8 votes

Hierarchies in regular languages

I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract): Guillaume Bonfante, Florian Deloup: The genus of regular languages. From the ...
Damiano Mazza's user avatar
8 votes
Accepted

(N)DFA with same initial/accepting state(s)

This question is solved for deterministic automata and for unambiguous automata in the book [1] [1] J. Berstel, D. Perrin, C, Reutenauer, Codes and automata, Vol. 129 of Encyclopedia of Mathematics ...
J.-E. Pin's user avatar
  • 4,771
8 votes
Accepted

Is it decidable whether the output length of a transducer is bounded by the input length?

The other contributor deleted his answer, maybe to let me extend my above comment, so here it is. Let $T$ be a possibly nondeterministic transducer, and $L$ be a regular language. Modify $T$ into a ...
Michaël Cadilhac's user avatar
7 votes
Accepted

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

A bit overkill, but: this paper shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have ...
Boson's user avatar
  • 560
7 votes

Complexity of checking if two words have an interleaving in a language

For a word $w=w_1\ldots w_{\ell}$ and for two integers $i,j$ with $1\le i\le j\le \ell$ we denote by $w(i,j)$ the subword $w_iw_{i+1}\ldots w_j$ of $w$. Furthermore we let $w(0,0)$ denote the empty ...
Gamow's user avatar
  • 5,772
7 votes
Accepted

Testing whether letters can be scheduled to achieve a word in a regular language

The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words: $x111$, $x000$, $y100$, $y010$, $y001$, $00c11$, $01c10$, $10c01$, and $11c00$ The reduction is ...
Mikhail Rudoy's user avatar
7 votes
Accepted

Complexity of DFA intersection in this specific case?

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$. For the upper bound, it suffices to observe that if $B$ ...
J.-E. Pin's user avatar
  • 4,771
7 votes
Accepted

Kleene Algebra for star-free regular expressions

You might be interested in bounded synchronization delay expressions. See [1] for details on these expressions. To sum up, they are equivalent to star-free expressions, but instead of using complement,...
Denis's user avatar
  • 8,598
7 votes
Accepted

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

Here is a proposition for an elementary proof: Let $\mathcal A=(A,Q,q_0,F,\delta)$ be a DFA for $L$, we want to build a DFA $\mathcal A'=(A,Q',q_0',F',\delta')$ for $f^{-1}(L)$. Intuitively, when ...
Denis's user avatar
  • 8,598
7 votes
Accepted

Regular Expressions that converts into unambiguous automata

The paper Ambiguity in Graphs and Expressions (Book et al., 1971) discusses constructing regular expressions that preserve the ambiguity of the input NFA and vice versa. That is, they give a ...
MRC's user avatar
  • 389
7 votes
Accepted

star height of star-free languages

The examples of arbitrary star-height given on the wikipedia page on the star-height problem are star-free: On arbitrary alphabet: :\begin{alignat}{2} e_1 &= a_1^* \\ e_2 &= \left(a_1^*a_2^*...
Denis's user avatar
  • 8,598
6 votes

minimizing size of regular expression

It is PSPACE-complete to decide whether an expression accepts all words, i.e. is equivalent to $(a|b|c|...)^*$. It is not hard to get convinced that in this proof of PSPACE-completeness (see e.g. ...
Denis's user avatar
  • 8,598
6 votes
Accepted

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

The paper [HP06] is in the spirit of your idea, although in a different direction, in the context of infinite words. It can be adapted more easily to finite words. In the powerset construction, we ...
Denis's user avatar
  • 8,598

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