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 (44)

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

This page was built for publication: An Approach to a Unified Theory of Automata