The automata-theory tag has no usage guidance.

**12**

votes

**1**answer

574 views

### Complementation of $\omega$-regular languages in reverse mathematics

Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over ...

**5**

votes

**2**answers

648 views

### A special class of regular languages: “circular” languages. Is it known?

We can define a subclass of the regular languages. Fix an alphabet $\Sigma$. Define the "circular" languages (actually, the name already exists to denote a different thing it seems, used in the field ...

**3**

votes

**3**answers

488 views

### 'Closure' of CFLs under complementation and intersection

Consider two context-free languages $L_1, L_2$. Of course, $L_1 - L_2, L_1\cap L_2, \bar{L}_1$, etc. are not necessarily context-free, but they are context-sensitive (the second is easy, the other two ...

**0**

votes

**1**answer

255 views

### A Nomenclature Issue : Imprimitive Semigroup?

The following question was asked by me on the forum sci.math.research,
“An imprimitive group is a transitive permutation group with a non-trivial
equivalence relation compatible with the action of ...

**7**

votes

**3**answers

1k views

### Wolfram's 2-state 3-symbol Turing machine

A few years ago it was announced that a 2-state symbol Turing machine was proven to be universal. However, Vaughn Pratt disputed the proof, and I gather he still disputes it. Wolfram's prize committee ...

**5**

votes

**0**answers

187 views

### “Question-answer” bisimulation

I often come across relations that would be defined as a bisimulation, except that the label match can be "inexact", that is, in the bisimulation game, a move labelled with "a" can be replied to with ...

**1**

vote

**1**answer

200 views

### Dumb question about Minimization in IATLC

I have probably a pretty dumb question about the classical Minimization algorithm for a DFA, as described in the Hopcroft book "Introduction to Automata Theory, Languages and Computation", pg. ...

**3**

votes

**5**answers

1k views

### Theory mainly concerned with $\lambda$-calculus?

Automata theory is mainly concerned with Turing machines and all its relatives-in-spirit. $\lambda$-calculus is rather rarely mentioned in textbooks on automata theory.
What's the common name of the ...

**21**

votes

**1**answer

741 views

### Automatic groups - recent progress

Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental ...

**7**

votes

**6**answers

2k views

### Regular languages and the pumping lemma

In certain dark corners of computer science and group theory, one often wants to prove that a language is not a regular language (ie a language accepted by a finite state automaton).
The only ...