24
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 stronger theorem and then the simple answer will follow.
Theorem: If we can solve the intersection non-emptiness problem for two DFA's in $O(n^{\delta})$ time,...
20
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 exponentially many of these to find the "needle in the haystack". (This is even if the learner knows in advance that the target automaton is of this form.) For a ...
19
About Q1:
Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable. Here are the original references:
The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and ...
17
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}^0$ reduction (and even with a more restrictive reduction actually).
In particular this shows that regular languages are not in $\textrm{TC}^0$ if $\textrm{...
16
There is even a stronger result than your request:
There are exponentially-ambiguous NFAs for which the minimal polynomially-ambiguous NFAs are exponentially larger, and in particular the minimal UFAs.
Check this paper by Hing Leung.
16
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
$L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$.
Concatenation hierarchies are defined by alternating Boolean operations and polynomial ...
15
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 uniform width-5 branching programs). Thus, any such language is not in $\mathrm{TC}^0$ unless $\mathrm{TC}^0=\mathrm{NC}^1$.
My favorite $\mathrm{NC}^1$-...
14
I think the IJFCS'05 paper by Leung: Descriptional complexity of nfa of different ambiguity
provides an example with a family of NFA accepting finite languages that involve an exponential blowup for "disambiguation" (in the proof of Theorem 5).
What is more, those automata have a special structure (DFA with multiple initial states).
14
Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define
$$
rank(u) = \begin{cases}
u &\text{if $u \in L$} \\
0 &\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ ...
14
Finite automata in which the initial state is also the unique accepting state have the form $r^∗$, where $r$ is some regular expression. However, as J.-E. Pin points out below, the converse is not true: there are languages of the form $r^*$ which are not accepted by a DFA with a unique accepting state.
Intuitively, given a sequence of states $q_0, \ldots, ...
14
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 for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$.
It is indeed hard to find a modern readable PSPACE-hardness proof for regular ...
12
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 = \{Q, \Sigma, \delta, q_0, F \}$, $|Q| = n$ )
Clearly $\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$ (simply use dead states)
To show the proper inclusion $\...
11
As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:
$$
d(l, k) = \left\{ \begin{array}{ll}
0 & \mbox{if } l = k \\
2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\}
\end{array}
\right.
$$
Roughly speaking, if a string ...
11
The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:
Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.
It's easy to see that $L$ is regular while $L'$ is not even context free.
L'' also isn't regular either, by the link @Sylvain posted in his ...
11
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 assume you mean finite automaton.
Then I claim that either the maximum bit density is achieved by a word of length < n, the number of states, or it is ...
11
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 paywall it would be great. I requested the full-text on ResearchGate.
Title: Which Finite Monoids are Syntactic Monoids of Rational omega-Languages.
Authors: ...
11
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 M$. Define the congruence relation $\equiv_Y$ over $M$ by $x \equiv_Y y$ iff $\big[\forall w, z \in M$, $wxz \in Y \Leftrightarrow wyz \in Y\big]$.
Definition:...
11
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 disjunctive if and only if the syntactic congruence of $P$ in $M$ is the equality relation. Thus a monoid is the syntactic monoid of a language if and only if it ...
11
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 a_{\sigma(n)}$ is
also in $L$.
Now, my understanding of your question is the following:
given a finite deterministic automaton $\mathcal{A}= (Q, A, \...
10
As you pointed out, there are several ways to define minimal transducers, but I only know of two mathematically appealing definitions.
The first result concerns the reduction of linear representations of recognizable series
(= defined by weighted automata). The best reference is Chapter II, Minimization, in one of these two books (the more recent is an ...
10
An important subclass of this family is a sub-class of 0-reversible languages. A language is 0-reversible if the reversal of the minimal DFA for the language is also deterministic. The reversing operation is defined as swapping initial and final states, and inverting the edge relation of the DFA. This means that a 0-reversible language can have only one ...
10
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 given many statements, usually in special cases.
[1] C. C. Elgot and J. E. Mezei, On relations defined by generalized finite automata, IBM J. Res. and ...
9
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 of strings in regular languages.
In ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 551–557, 1995.
9
Let me add a concrete example to the excellent answer of Jeffrey Shallit.
Suppose you want to create a Scrabble (TM) dictionary. You can think of several ways to represent your dictionary, like list of words, tries (letter trees) or deterministic automata. According to [1], minimizing a trie to a dawg [= DFA] produces an amazing savings in space; the number ...
9
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, R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. ...
9
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 automaton requires a finite alphabet, and only finitely many symbols can actually appear in a single regular expression. So, specifically for the context of regular ...
9
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 there exists $a \in \Gamma$ such that $h = f_a \circ g$. Then, testing whether a function $g$ is in $G$ reduces to testing whether $g$ is reachable in the ...
9
$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$ is NP-hard. [1]
[1] E.M. Gold. Complexity of Automaton Identification from Given Data. Information and Control, 37, 302-320 (1978)
8
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 and its Applications, Cambridge University Press, 2009.
In the case of deterministic automata, the characterization is given in Proposition 3.2.5. Recall that a ...
8
The regular languages inside $AC^0$ are a "nice" subset of the regular languages. They have nice logical as well as algebraic characterizations.
The book "Finite Automata, Formal Logic and Circuit Complexity" by Straubing considers these questions.
Your question can be answered as follows.
$AC^0 \cap REG$ = $FO[<,Suc,\equiv]$ = languages recognized by ...
Only top voted, non community-wiki answers of a minimum length are eligible
