44 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite ...
user avatar
  • 7,653
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or ...
user avatar
  • 3,741
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 ...
user avatar
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 ...
user avatar
  • 10k
19 votes
Accepted

Quadratic relationship between nondeterministic and deterministic space?

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that ...
user avatar
18 votes
Accepted

Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

Perhaps I found some relevant information in: Jean-Michel Autebert, Jean Berstel, Luc Boasson; Context-Free Languages and Pushdown Automata; Handbook of Formal Languages; 1997, pp 111-174 DPDAs ...
user avatar
18 votes
Accepted

Is Hartmanis-Stearns conjecture settled by this article?

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn". Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
user avatar
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}...
user avatar
  • 992
17 votes
Accepted

For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is in P if $L(\alpha)$ is finite; coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\...
user avatar
  • 188
16 votes
Accepted

What notable automaton models have polynomially-decidable containment?

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
15 votes
Accepted

Regular language that discriminates between two deterministic CFGs

Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable. The class of visibly pushdown languages is a ...
user avatar
14 votes

What notable automaton models have polynomially-decidable containment?

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a ...
user avatar
  • 7,653
14 votes
Accepted

Are regular languages closed under addition?

Yes, they are. First, consider the alphabet $\Sigma_i^3$ whose symbols are triples of digits (stacked one above each other into a pile of three digits). Over this alphabet, we can define a regular ...
user avatar
14 votes
Accepted

Novel proof of pumping lemma for regular languages

Essentially the same argument is made by Andries P.J. van der Walt (1976, Lemma 2.3 and Example 2.9) for the variant of the pumping lemma where $N$ letters are marked and all three of $x$, $y$, $z$ ...
user avatar
  • 3,314
13 votes

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer. 1. The case of finite ...
user avatar
  • 4,721
13 votes
Accepted

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

It is NP-hard for $k=3$. The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses. First of all, for simplicity, let's ...
user avatar
  • 13.5k
12 votes
Accepted

Lower bound for NFA accepting 3 letter language

The bounds... We have in fact $NFA(L) \ge Cov(M) + Cov(N)$, see Theorem 4 in (Gruber & Holzer 2006). For an upper bound, we have $2^{Cov(M)+Cov(N)} \ge DFA(L) \ge NFA(L)$, see Theorem 11 in the ...
user avatar
12 votes
Accepted

Minimizing Automata accepting $\omega$-words (i.e. infinite words)

In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ ...
user avatar
  • 5,261
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 = \{...
user avatar
12 votes

Determinising unambiguous automata without exponential blowup

No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows: Consider the alphabet $\{a,b\}$, and the language: $$L_k=\{w\in \{a,b\}^*:\text{the ...
user avatar
  • 5,261
11 votes

What notable automaton models have polynomially-decidable containment?

A Non deterministic XOR automaton (NXA) fits your question. A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor ...
user avatar
  • 9,378
11 votes

Conjecture about two counters automata

So people keep nagging me to post this even though it only solves a simplified version of the problem. Okay then :) At the end of this, I will put some of what I learned from the paper of Ibarra and ...
user avatar
11 votes
Accepted

Can we approximate the number of words accepted by an NFA?

There exists a FPRAS (Fully Polynomial Randomized Approximation Scheme) for the problem of counting the words of length $n$ accepted by a NFA in the general case (without restricting to the acyclic ...
user avatar
  • 521
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 ...
user avatar
11 votes
Accepted

Finding the smallest DFA that separates two words without using brute force search?

If I had to do this in practice, I would use a SAT solver. The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance. For ...
user avatar
  • 10.4k
11 votes
Accepted

Is there a survey of the field of quantum automata?

You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions. Moreover, here is a list ...
user avatar
11 votes
Accepted

Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

You don't need nondeterminism or multiple heads. Even a 2DPDA can accept this language: push 2 counters per symbol while scanning from left endmarker to right; then pop 3 per symbol while scanning ...
user avatar
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 ...
user avatar
  • 7,653

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