A NEW AUTOMATON MODEL FOR TAGS: 2‐SA
Tilman Becker · Computational Intelligence · 1994
In this paper, we introduce and define a new class of automata (pushdown automata with n stacks, abbreviated as n‐SA). The ultimate aim is to give a new characterization of LCRFL, the class of languages accepted by a linear context‐free rewriting system (LCFRS). In particular, we introduce 2‐SA as a new automaton model for tree‐adjoining grammars (TAG). In the simplest cases (0‐SA and 1‐SA), the languages that are accepted by the automata are the regular and context‐free languages respectively. A more complex case is the case of a 2‐SA which accepts TALs. The n‐SA creates an infinite hierarchy of languages and it seems that this hierarchy corresponds to others in the class LCFRL. The 2‐SA corresponds closely to the EPDA (embedded pushdown automaton, an automaton model equivalent to TAGs). Unlike the EPDA, which allows push operations “below the top stack,” an n‐SA allows push and pop operations only on the top of their (multiple) stacks. So n‐SA trade simpler operations against an also simpler but expanded storage structure.