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
27 votes
Accepted

Number of words of length n in a context-free language

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser: Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$ Or there ...
user avatar
  • 5,712
18 votes

Irreducible languages

There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this ...
user avatar
  • 1,377
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
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
Accepted

Decide the existence of a string homomorphism

It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci. 21 (1980), 46-62. Look at ...
user avatar
16 votes
Accepted

What is the name of a function $f$ such that $f(x,y) \in L \iff x\in L \wedge y \in L$?

They are typically called AND-functions. (I'm not joking.) Indeed, this concept has been considered before, and that's what people call them. See, for example, the book by Kobler, Schoning, and Toran ...
user avatar
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
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

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,324
14 votes

Irreducible languages

Another paper to look at: Kai Salomaa, "Language Decompositions, Primality, and Trajectory-Based Operations", 2008.
user avatar
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

Translation of context-free parsing into SAT

(I guess the important word in the original question is ``published''.) There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in Roland Axelsson, Keijo Heljanko, and ...
user avatar
  • 3,324
13 votes
Accepted

"Embedding" a language in itself

This question is related to the so called insertion systems. An insertion system is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$...
user avatar
  • 4,721
13 votes
Accepted

Is the Set of all Primitive Words a Prime Language?

The answer is yes. Suppose we have a factorization $Q = A\cdot B$. One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $...
user avatar
13 votes
Accepted

Ambiguity of regular expressions

Yes, every regular expression can be converted into an unambiguous one by converting to a DFA and then to a regular expression. And no, there aren't any inherently ambiguous regular languages in the ...
user avatar
12 votes
Accepted

Bounds on size of self-concatenation of Finite Languages

You can show $ |L|^i $ is a tight upper bound by using the following language: $ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $ Any concatenation gives a new string. For a lower bound, I can ...
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
Accepted

What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies $$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$ for every ...
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
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

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
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 ...
user avatar
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 ...
user avatar
  • 4,721
11 votes
Accepted

Size of complement of context-free language

From the proof that determining if a CFL ${L}$ = $\Sigma^*$ is undecidable, the set of strings $ID_0\#ID_1^R\#ID_2\#ID_3^R\#\ldots\#ID_t$ where $ID_0,ID_1,\ldots,ID_t$ is a list of the configurations ...
user avatar
11 votes
Accepted

Is the complement of { www | … } context-free?

Still CFL I believe, with an adaptation of the classical proof. Here's a sketch. Consider $L = \{xyz : |x|=|y|=|z| \land (x \neq y \lor y \neq z)\}$, which is the complement of $\{www\}$, with the ...
user avatar
11 votes

NP-complete decision problems on deterministic automata

The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete: Input: Integer $k$ and sets $...
user avatar
11 votes
Accepted

Example of an context-sensitive language with a specific number of words of length $n$

The language $$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$ is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\...
user avatar

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