One-way stack automata
From MaRDI portal
Publication:5557460
DOI10.1145/321386.321403zbMath0171.14803OpenAlexW1982449618WikidataQ56059678 ScholiaQ56059678MaRDI QIDQ5557460
Michael A. Harrison, Seymour Ginsburg, Sheila A. Greibach
Publication date: 1967
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321386.321403
Related Items
Alternating and empty alternating auxiliary stack automata. ⋮ The theory of languages ⋮ Unnamed Item ⋮ Petri net algorithms in the theory of matrix grammars ⋮ Prediction of infinite words with automata ⋮ Unnamed Item ⋮ Quasi-realtime languages ⋮ Grammars, derivation modes and properties of indexed and type-0 languages ⋮ The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index ⋮ Somewhat finite approaches to infinite sentences. ⋮ The theory of languages ⋮ Deterministic Stack Transducers ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Visit-bounded stack automata ⋮ Familles de langages fermées par crochet ouvert ⋮ A grammatical characterization of alternating pushdown automata ⋮ Unnamed Item ⋮ Characterizations of transductions defined by abstract families of transducers ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Multi-stack-counter languages ⋮ On store languages and applications ⋮ The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors ⋮ One-way weak-stack-counter automata ⋮ HYBRID EXTENDED FINITE AUTOMATA ⋮ Tree-walking-storage automata ⋮ Self-verifying Cellular Automata ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ Queue Automata: Foundations and Developments ⋮ A note on decision problems for three-way two-dimensional finite automata ⋮ Between SC and LOGDCFL: families of languages accepted by polynomial-time logarithmic-space deterministic auxiliary depth-\(k\) storage automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tree-stack automata ⋮ Deterministic Input-Reversal and Input-Revolving Finite Automata ⋮ Description of restricted automata by first-order formulae ⋮ Iterated stack automata and complexity classes ⋮ Further remarks on DNA overlap assembly ⋮ Cayley automata ⋮ Accepting runs in a two-way finite automaton ⋮ Removing nondeterminism in constant height pushdown automata ⋮ $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$ ⋮ Observations about bounded languages and developmental systems ⋮ Decidability of code properties ⋮ 1-way stack automaton with jumps ⋮ Deep pushdown automata ⋮ Reversal-bounded multipushdown machines ⋮ A CUCH-machine: The automatic treatment of bound variables ⋮ Visit-bounded stack automata ⋮ Characterization theorems on abstract families of transducers ⋮ Finite automata with multiplication ⋮ Degree-languages: A new concept of acceptance ⋮ Control sets on context-free grammar forms ⋮ On store languages of language acceptors ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ Stack languages and log n space ⋮ A note on cyclic closure operations ⋮ On computational complexity of set automata ⋮ Some decision problems concerning sequential transducers and checking automata ⋮ Monadic recursion schemes: The effect of constants ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Set Automata ⋮ Deterministic stack automata and the quotient operator ⋮ Checking automata and one-way stack languages ⋮ Scattered context grammars ⋮ Diving into the queue ⋮ What makes some language theory problems undecidable ⋮ Syntactic operators on full semiAFLs ⋮ Principal abstract families of weighted tree languages ⋮ Deterministic Stack Transducers ⋮ CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS ⋮ Finite-turn checking automata ⋮ Absolutely parallel grammars and two-way finite-state transducers ⋮ Pushdown cellular automata ⋮ On the extension of Gladkij's theorem and the hierarchies of languages ⋮ On input-revolving deterministic and nondeterministic finite automata ⋮ Context free normal systems and ETOL systems ⋮ SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS ⋮ A note on self-modifying finite automata ⋮ Theory of formal grammars ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ Homomorphic characterizations of recursively enumerable languages with very small language classes ⋮ Sublogarithmic ambiguity ⋮ A homomorphic characterization of recursively enumerable languages ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ Extended macro grammars and stack controlled machines ⋮ A note on undecidable properties of formal languages ⋮ Control sets on grammars ⋮ Some restrictions onW-grammars
This page was built for publication: One-way stack automata
