# Tag Info

### 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 ...
• 7,653
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 ...
• 3,741
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

### 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
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 ...
• 6,888
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 ...
• 22.3k
Accepted

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 ...
• 6,888
Accepted

• 188
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 ...
• 5,424

• 22.3k

### 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 ...
• 5,261

### 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 ...
• 9,378

### 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 ...
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 ...
• 521
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
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 ...
• 10.4k
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 ...
• 3,647
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 ...
• 6,888
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 ...