39
A quick check of the sources reveals that Chomsky called the levels of his hierarchy just “type 0, type 1, type 2, type 3”. He mentions in a footnote that his type 3 corresponds to “regular events” of Kleene. Kleene wrote there: We shall presently describe a class of events which we will call "regular events." (We would welcome any suggestions as to a more ...
answered Oct 26 '11 at 16:49
Emil Jeřábek supports Monica
11k3 gold badges41 silver badges64 bronze badges
24
The following paper seems to contain an answer:
Mix Barrington, D. A., Compton, K., Straubing, H., Therien, D.: Regular languages in $\mathsf{NC}^1$. Journal of Computer and System Sciences 44(3), 478-499 (1992) (link)
One of the characterizations obtained there is as follows. The class $\mathsf{REG} \cap \mathsf{AC}^0 \subset \{0, 1\}^*$ contains exactly ...
22
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 ...
18
There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:
Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
by Bart Jacobs
A Bialgebraic Approach to Automata and Formal Language Theory by James Worthington.
In the first of these papers, the structure of ...
18
State complexity is really about concise description of an object (in this case, a regular language), not about computational complexity. The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and ...
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.
15
Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)
If every iterative/pumping pair of a context-free language L is
degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was ...
15
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{...
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
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
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
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$-...
answered Jan 2 '16 at 18:21
Emil Jeřábek supports Monica
11k3 gold badges41 silver badges64 bronze badges
14
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 ...
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
Actually, I think what you're looking for is Kleene algebra. See Dexter Kozen's classic article. He gives an axiomatization of Kleene-star. I assume this is the very first step you're interested in.
A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110(2):366-390, May 1994.
That article does not ...
12
FO(LFP) captures PTIME on ordered structures, and strings are ordered structures. So the languages definable by FO(LFP) include all regular languages and much much more.
http://dx.doi.org/10.1016/S0019-9958(86)80029-8
Ebbinghaus and Flum's textbook contains an exercise that asks to show FO(TC^1) (first-order logic extended with transitive closures of ...
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
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
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
Even if we require that the expressions are "human-readable", and the conversion between the standard notation and the new notation is fairly easy to compute, the answer is "yes".
For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:
You are allowed to remove any prefix that consists of a sequence of ('s
...
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
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
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 ...
10
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
