Complexity results for prefix grammars

DOI10.1051/ita:2005024zbMath1133.68357OpenAlexW1980155685MaRDI QIDQ3025324

Markus Lohrey, Holger Petersen

Publication date: 13 July 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_2_391_0

zbMATH Keywords

computational complexityrewriting systemsregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Thue and Post systems, etc. (03D03)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the regular structure of prefix rewriting
• Complete problems for deterministic polynomial time
• Prefix grammars: An alternative characterization of the regular languages
• Model checking LTL with regular valuations for pushdown systems
• Alternating Pushdown and Stack Automata
• Alternation
• Regular canonical systems
• A Note on Pushdown Store Automata and Regular Systems
• Canonical systems which produce periodic sets

This page was built for publication: Complexity results for prefix grammars