An Approach to a Unified Theory of Automata

DOI10.1002/j.1538-7305.1967.tb03172.xzbMath0155.34303OpenAlexW1973145926MaRDI QIDQ5536637

John E. Hopcrofts, Jeffrey D. Ullman

Publication date: 1967

Published in: Bell System Technical Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/j.1538-7305.1967.tb03172.x

zbMATH Keywords

mathematical logic

Related Items

The theory of languages, A general theory of translation, Equational derivation vs. computation, On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes, Quasi-realtime languages, The theory of languages, Chains of full AFL's, On locating minimum feedback vertex sets, Characterizations of transductions defined by abstract families of transducers, New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines, Pebble minimization: the last theorems, Synthesizing Computable Functions from Rational Specifications Over Infinite Words, The derivational complexity of string rewriting systems, One-way acceptors and languages, On generalized zeta functions of formal languages and series, A note on the space complexity of some decision problems for finite automata, Iterated stack automata and complexity classes, AUTOMATA AND DIGITAL COMPUTERS, Gurevich-Harrington's games defined by finite automata, Regular combings, nonpositive curvature and the quasiconvexity of Abelian subgroups, Unnamed Item, Abstract families of relations, \(X\)-automata on \(\omega\)-words, Automatic correction of syntax-errors in programming languages, A generalized mathematical theory of structured programming, Abstract families of length-preserving processors, On computational complexity of set automata, Linear weighted tree automata with storage and inverse linear tree homomorphisms, Deterministic stack automata and the quotient operator, The power of two-way deterministic checking stack automata, What makes some language theory problems undecidable, Writing pushdown acceptors, Time- and tape-bounded Turing acceptors and AFLs, Periodicities on trees, Abstract families of processors, A characterization of two-way deterministic classes of languages, Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, Characterizations and computational complexity of systolic trellis automata, Automata equipped with auxiliary data structures and regular realizability problems, The many faces of a translation, A note on off-line machines with 'Brownian' input heads, Extended macro grammars and stack controlled machines, On restarting automata with auxiliary symbols and small window size, Query automata over finite trees