Endmarkers can make a difference

DOI10.1016/0020-0190(90)90063-4zbMath0697.68075OpenAlexW2015546730MaRDI QIDQ911789

Moshe Y. Vardi

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90063-4

zbMATH Keywords

formal languagestheory of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (3)

Regular language representations in the constructive type theory of Coq ⋮ From bidirectionality to alternation. ⋮ Two-Way Automata in Coq

Cites Work

• Hierarchies of complete problems
• Space-bounded reducibility among combinatorial problems
• Unnamed Item

This page was built for publication: Endmarkers can make a difference