Tag Systems and the Complexity of Simple Programs

DOI10.1007/978-3-662-47221-7_2zbMath1432.68143MaRDI QIDQ5500609

Turlough Neary, Damien Woods

Publication date: 7 August 2015

Published in: Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01442479/file/338243_1_En_2_Chapter.pdf

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q80: Cellular automata (computational aspects)

68Q42: Grammars and rewriting systems

68Q04: Classical models of computation (Turing machines, etc.)