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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...