
A language over a finite alphabet is called \(n\)-tape real-time if it is recognizable by an \(n\)-tape deterministic real-time Turing machine. (For \(n=0\) such a machine is just a deterministic finite automaton.) \textit{M.~Rabin} [Isr. J. Math. 1, 203--211 (1963; Zbl 0156.25603)] gave an example of a language which was 2-tape real-time but not 1-tape real-time. The word problem of \(F_2\), the free group of rank 2, is known to be 1-tape real-time. The authors prove that the word problem of \(F_2\times F_2\) is 2-tape real-time but not 1-tape real-time. It is also proven that the word problem of the restricted wreath product of a finite group with an infinite cyclic group is 1-tape real-time. The authors show that for all \(r\neq 0\) the word problem of the Baumslag-Solitar group \(\langle x,y\;| \;y^{-1}xy=x^r\rangle\) is 5-tape real-time.
restricted wreath product, Turing machines and related notions, word problem of a group, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), multitape real-time Turing machine, QA, Word problems, etc. in computability and recursion theory
restricted wreath product, Turing machines and related notions, word problem of a group, Word problems, other decision problems, connections with logic and automata (group-theoretic aspects), multitape real-time Turing machine, QA, Word problems, etc. in computability and recursion theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
