Size complexity of rotating and sweeping automata

DOI10.1016/j.jcss.2011.06.004zbMath1242.68146MaRDI QIDQ414916

Tobias Mömke, Richard Královič, Christos A. Kapoutsis

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.06.004

zbMATH Keywords

randomization; finite automata; size complexity; self-verification; hardness propagation; sweeping automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)