Nested Stack Automata

DOI10.1145/321526.321529zbMath0184.28603DBLPjournals/jacm/Aho69OpenAlexW2027529581WikidataQ56016699 ScholiaQ56016699MaRDI QIDQ5576259

A. V. Aho

Publication date: 1969

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321526.321529

zbMATH Keywords

languages, automata, networks

Related Items (51)

The grammar of mammalian brain capacity ⋮ Pushdown machines for the macro tree transducer ⋮ On the rational subset problem for groups. ⋮ EDT0L grammars with only one variable have tractable generating functions ⋮ Queue Automata: Foundations and Developments ⋮ Stochastic grammars and languages ⋮ Unnamed Item ⋮ Tree-stack automata ⋮ Queues, stacks, and transcendentality at the transition to chaos ⋮ Multidimensional trees ⋮ GROUPS WITH CONTEXT-FREE CONJUGACY PROBLEMS ⋮ Iterated stack automata and complexity classes ⋮ A shrinking lemma for indexed languages ⋮ An implementation of syntax directed functional programming on nested- stack machines ⋮ The equivalence problem for real-time deterministic pushdown automata ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Pushdown tree automata ⋮ Die mit Nestedstackautomaten Berechenbaren Funktionen sind Elementar ⋮ Abstract families of relations ⋮ Two-way nested stack automata are equivalent to two-way stack automata ⋮ Iterated pushdown automata and sequences of rational numbers ⋮ Basic tree transducers ⋮ Look-ahead on pushdowns ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Augmented transition networks and their relation to tree transducers ⋮ A generalized approach to formal languages ⋮ Weighted automata with storage ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ A new pumping lemma for indexed languages, with an application to infinite words ⋮ Stack languages and log n space ⋮ On finite-index indexed grammars and their restrictions ⋮ Generators of regular languages ⋮ An Automata Characterisation for Multiple Context-Free Languages ⋮ Diving into the queue ⋮ The calculi of emergence: Computation, dynamics and induction ⋮ Principal AFL ⋮ On the existence of generators for certain AFL ⋮ On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems ⋮ Principal abstract families of weighted tree languages ⋮ Regular sets over extended tree structures ⋮ GROUPS WITH INDEXED CO-WORD PROBLEM ⋮ Theory of formal grammars ⋮ Hierarchies of hyper-AFLs ⋮ Tree pushdown automata ⋮ Pushdown tree automata, algebraic tree systems, and algebraic tree series ⋮ Model-Checking Games for Typed λ-Calculi ⋮ Extended macro grammars and stack controlled machines ⋮ Decidability of EDT0L structural equivalence ⋮ COMBING NILPOTENT AND POLYCYCLIC GROUPS ⋮ Some restrictions onW-grammars ⋮ Macro tree transducers

This page was built for publication: Nested Stack Automata