Revision as of 11:37, 23 December 2024 edit Jochen Burghardt (talk \| contribs) Extended confirmed users 24,302 edits →Example: re-insert "class=wikitable" (removed 6 Dec 2018), in order to clarify what are the symbols (some of them are composed of two charcters) ← Previous edit		Latest revision as of 16:57, 24 March 2025 edit undo 129.93.161.228 (talk) →Properties: clarified the Gilman-Shapiro result & connected it to the Muller-Schupp theorem
Line 114: When automata are allowed to re-read their input ("[[Two-way automaton\|two-way automata]]"), nested stacks do not result in additional language recognition capabilities, compared to plain stacks.<ref>{{cite journal \|last1=Beeri \|first1=C. \|title=Two-way nested stack automata are equivalent to two-way stack automata \|journal=Journal of Computer and System Sciences \|date=June 1975 \|volume=10 \|issue=3 \|pages=317–339 \|doi=10.1016/s0022-0000(75)80004-3 \|doi-access=free }}</ref> Gilman and Shapiro used nested stack automata to solve the [[Word problem for groups\|word problem]] in ~~certain~~[[Virtually#Virtually_free\|virtually free]] [[Group (mathematics)\|groups]], similarly to the [[Muller–Schupp theorem]].<ref>{{cite tech report \|last1=Shapiro \|first1=Robert Gilman Michael \|title=On groups whose word problem is solved by a nested stack automaton \|date=4 December 1998 \|arxiv=math/9812028 \|s2cid=12716492 \|citeseerx=10.1.1.236.2029 }}</ref> ==Notes==

Nested stack automaton: Difference between revisions