Transformational methods and their application to complexity problems
From MaRDI portal
Publication:1227002
DOI10.1007/BF00263746zbMath0329.02015OpenAlexW1985677568MaRDI QIDQ1227002
Publication date: 1976
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00263746
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)
Related Items
Gradually intractable problems and nondeterministic log-space lower bounds ⋮ Halting space-bounded computations ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Multihead two-way probabilistic finite automata ⋮ On the descriptional power of heads, counters, and pebbles ⋮ The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet ⋮ Multihead two-way probabilistic finite automata ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ Variations on the technique of Ďuriš and Galil ⋮ Multi-head finite automata: Data-independent versus data-dependent computations
This page was built for publication: Transformational methods and their application to complexity problems
