23
votes
Accepted
Deciding emptiness of intersection of regular languages in subquadratic time
Simple answer: If there does exist a more efficient algorithm that runs in $O(n^{\delta})$ time for some $\delta < 2$, then the strong exponential time hypothesis would be refuted.
We will prove a ...
- 4,900
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 ...
- 10k
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}...
- 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
$...
- 4,721
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 ...
- 14.8k
14
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 ...
- 7,653
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 = \{...
- 22.3k
11
votes
Accepted
computing maximal bit density over a FSM
First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00 where there is no max. (The sup may not be attained.)
Second, by "FSM" I ...
- 6,888
11
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 ...
- 7,653
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 ...
- 3,816
11
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 ...
- 4,721
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 ...
- 4,721
10
votes
Accepted
Who introduced nondeterministic M-automata, and proved that the finite ones recognize the rational sets over M?
According to J. Sakarovich, Elements of Automata Theory, p. 372,
It seems that the result appears for the first time in [1]; hidden in a footnote of this seminal but difficult article, it was then ...
- 4,721
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 ...
- 161
9
votes
Deciding whether a context-free language is regular
Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.
Regarding DCFL, I have two references (from Hopcroft+Ullman 79):
A regularity test for pushdown machines, ...
- 1,502
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 ...
- 50.2k
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 ...
- 10.4k
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$ ...
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, ...
- 5,424
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 ...
- 3,816
8
votes
Accepted
minimal finite automata given in-words and out-words
If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete
Gold1978 - Complexity of Automaton ...
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 ...
- 4,721
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 ...
- 4,823
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 ...
- 6,888
7
votes
Complexity of intersection of regular languages as context-free grammars
This is a great question and it really lies within my interests. I'm glad that you asked it Max.
Let $n$ DFA's with at most $O(n)$ states each be given. It would be nice if there existed a PDA with ...
- 4,900
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 ...
- 550
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 ...
- 5,712
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 ...
- 2,718
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$ ...
- 4,721
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,...
- 7,653
Only top scored, non community-wiki answers of a minimum length are eligible