Content deleted Content added
mentioned two papers on nested stack automata; required distinction to embedded pushdown automata |
|||
Line 1:
In [[automata theory]], a '''nested stack automaton''' is a [[finite state machine|finite automaton]] that can make use of a [[Stack (data structure)|stack]] containing data which can be additional stacks.<ref name="aho"> {{cite journal | last = [[Alfred Aho|Aho]] | first = Alfred | year = 1969 | title = Nested stack automata | journal = [[Journal of the ACM]] | volume = 16 | issue = 3 | pages = 383–406 | issn = 0004-5411 | url = http://portal.acm.org/ft_gateway.cfm?id=321529&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=21501966&CFTOKEN=95121590 | doi = 10.1145/321526.321529 }} </ref> A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an [[indexed language]],<ref> {{cite book | last = [[Barbara Partee|Partee]] | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 | isbn = 978-90-277-2245-4 }} </ref> and in fact the class of indexed languages is exactly the class of languages accepted by one-way [[nondeterministic algorithm|nondeterministic]] nested stack automata.<ref name="aho" /> Nested stack automata should not confused with [[embedded pushdown automata]], which have less computational power.{{citation needed|reason=The claim is currently supported only by the order in which both notions appear in the 'Automata theory: formal languages and formal grammars' overview table below.}}
==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-339| url=http://www.sciencedirect.com/science/article/pii/S0022000075800043/pdf?md5=cfc9461ee21faf05c41631fecd104fa5&pid=1-s2.0-S0022000075800043-main.pdf}}</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| year=1998| month=Dec| pages=16| institution=arXiv| url=http://arxiv.org/pdf/math/9812028v1.pdf}}</ref>
==See also==
| |||