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

DOI10.1016/0020-0190(81)90044-2zbMath0474.68088OpenAlexW2078636695MaRDI QIDQ1158973

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

time complexitycontext-free languages

Mathematics Subject Classification ID

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

Related Items (2)

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

Cites Work

• Unnamed Item
• General context-free recognition in less than cubic time
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• On two-way multihead automata
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• 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

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