Comparing descriptional and computational complexity of infinite words

DOI10.1007/3-540-58131-6_46zbMath1529.68118OpenAlexW2115348183MaRDI QIDQ6183604

Juhani Karhumäki, Juraj Hromkovič, A. Lepistö

Publication date: 29 January 2024

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58131-6_46

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Iterated GSMs and CO-CFL
• Logical basis for information theory and probability theory
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part I
• Unnamed Item
• Unnamed Item

This page was built for publication: Comparing descriptional and computational complexity of infinite words