Premium
A NEW AUTOMATON MODEL FOR TAGS: 2‐SA
Author(s) -
Becker Tilman
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00006.x
Subject(s) - pushdown automaton , embedded pushdown automaton , deterministic pushdown automaton , computer science , context free language , rewriting , class (philosophy) , nested word , automaton , büchi automaton , tree automaton , deterministic context free grammar , two way deterministic finite automaton , tree (set theory) , context (archaeology) , discrete mathematics , theoretical computer science , programming language , deterministic automaton , mathematics , rule based machine translation , context free grammar , combinatorics , automata theory , parsing , quantum finite automata , nondeterministic finite automaton , tree adjoining grammar , artificial intelligence , paleontology , biology
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.