Unary Pushdown Automata and Straight-Line Programs

DOI10.1007/978-3-662-43951-7_13zbMath1409.68156arXiv1403.0509MaRDI QIDQ5167834

Rupak Majumdar, Dmitry Chistikov

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.0509

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q42: Grammars and rewriting systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)