The tag has no wiki summary.

learn more… | top users | synonyms

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 ...
19
votes
1answer
685 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 ...
6
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 ...