Content deleted Content added
m Dating maintenance tags: {{Merge-to}} |
Disambiguated: nondeterministic → nondeterministic algorithm using Dab solver |
||
Line 1:
{{merge-to|Embedded pushdown automaton|discuss=Talk:Nested stack automaton#Merge proposal|date=April 2012}}
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>
==See also==
|