Nested stack automaton: Difference between revisions

Revision as of 04:24, 19 July 2014

Revision as of 15:04, 30 May 2015

Line 108:

==Properties==

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| author=C. Beeri| title=Two-Way Nested Stack Automata Are Equivalent to Two-Way Stack Automata| journal=J. Comp. and System Sciences| year=1975| volume=10| pages=317-339317–339| url=http://www.sciencedirect.com/science/article/pii/S0022000075800043/pdf?md5=cfc9461ee21faf05c41631fecd104fa5&pid=1-s2.0-S0022000075800043-main.pdf| doi=10.1016/s0022-0000(75)80004-3}}</ref>

Gilman and Shapiro used nested stack automata to solve the [[Word problem for groups|word problem]] in certain [[Group (mathematics)|groups]].<ref>{{cite techreport| author=Robert Gilman, Michael Shapiro| title=On Groups Whose Word Problem is Solved by a Nested Stack Automaton|date=Dec 1998| pages=16| institution=arXiv| url=http://arxiv.org/pdf/math/9812028v1.pdf}}</ref>