Nested stack automaton: Difference between revisions

Revision as of 05:02, 30 January 2023

Latest revision as of 16:57, 24 March 2025

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Bots|deny=AWB}}<!--REASON: GenFixes incorrectly identifies the first "{" in "{[[empty string{{!}}ε]]}" as an unbalanced bracket & removes it-->

[[File:Pushdown-overview.svg|thumb|right|A nested stack automaton has the same devices as a [[pushdown automaton]], but has less restrictions for using them.]]

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 |last1=Aho |first1=Alfred V. |s2cid=685569 |authorlink1=Alfred Aho |title=Nested Stack Automata |journal=Journal of the ACM |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 |doi-access=free }}</ref>

Like a [[stack automaton]], a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.

Line 59 ⟶ 60:

An example run (input string not shown):

{| class=wikitable

{|

|-

! Action

Line 113 ⟶ 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 techreporttech 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==