The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
3answers
393 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
1answer
245 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
3answers
914 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
0answers
184 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
1answer
194 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
5answers
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 ...
20
votes
1answer
695 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
6answers
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 ...