scientific article; zbMATH DE number 3576701

MaRDI QIDQ4146255zbMATH OpenFDO

Authors I. H. Sudborough

Publication date 1977

Full work available at URL https://eudml.org/doc/92050

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Cites work

• A note on computing time for recognition of languages generated by linear grammars
• An observation on time-storage trade off
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Comparing complexity classes
• General context-free recognition in less than cubic time
• scientific article; zbMATH DE number 3468275 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3558991 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3569860 (Why is no real title available?)
• scientific article; zbMATH DE number 3586493 (Why is no real title available?)
• scientific article; zbMATH DE number 3640911 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3403734 (Why is no real title available?)
• Multi-tape and multi-head pushdown automata
• On non-determinacy in simple computing devices
• On tape-bounded complexity classes and multihead finite automata
• On the computational power of pushdown automata
• On two-way multihead automata
• Pushdown automata with counters
• Space-bounded reducibility among combinatorial problems
• The Hardest Context-Free Language
• Time and tape complexity of pushdown automaton languages
• Time bounded random access machines
• Translational lemmas, polynomial time, and \((\log n)^j\)-space

Cited in

(6)

• On efficient recognition of transductions and relations
• Hierarchies of one-way multihead automata languages
• Alternating multihead finite automata
• Refined simulation of multihead automata
• Some undecidable problems for parallel communicating finite automata systems
• scientific article; zbMATH DE number 3690693 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4146255)