Time complexity of languages recognized by one-way multihead pushdown automata

DOI10.1016/0020-0190(81)90044-2MaRDI QIDQ1158973zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter

Publication date 1981

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(81)90044-2

zbMATH Keywords

context-free languagestime complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• General context-free recognition in less than cubic time
• On two-way multihead automata
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Time and tape complexity of pushdown automaton languages

Cited in

(2)

• On efficient recognition of transductions and relations
• A note on two-way nondeterministic pushdown automata

This page was built for publication: Time complexity of languages recognized by one-way multihead pushdown automata

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