Nested stack automaton

Nested stack automaton

In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] 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.[2]

See also

References

  1. ^ Aho, Alfred (1969). "Nested stack automata". Journal of the ACM 16 (3): 383–406. doi:10.1145/321526.321529. ISSN 0004-5411. http://portal.acm.org/ft_gateway.cfm?id=321529&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=21501966&CFTOKEN=95121590. 
  2. ^ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Nested word — In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of… …   Wikipedia

  • Deterministic pushdown automaton — In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic… …   Wikipedia

  • Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… …   Wikipedia

  • List of mathematics articles (N) — NOTOC N N body problem N category N category number N connected space N dimensional sequential move puzzles N dimensional space N huge cardinal N jet N Mahlo cardinal N monoid N player game N set N skeleton N sphere N! conjecture Nabla symbol… …   Wikipedia

  • Indexed language — Indexed languages are a class of formal languages discovered by Alfred Aho [ cite journal | last = Aho | first = Alfred | year = 1968 | title = Indexed grammars an extension of context free grammars | journal = Journal of the ACM | volume = 15 |… …   Wikipedia

  • Sheila Greibach — (1939 ) is a researcher in formal languages, automata, compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles.She worked with Seymour Ginsburg… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”