Comparing descriptional and computational complexity of infinite words

DOI10.1007/3-540-58131-6_46MaRDI QIDQ6183604zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Juhani Karhumäki, 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

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

Recommendations

• scientific article; zbMATH DE number 1834659
• On the computational complexity of infinite words.
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Iterative devices generating infinite words
• The Kolmogorov complexity of infinite words

Cites work

• A formal theory of inductive inference. Part I
• scientific article; zbMATH DE number 3767068 (Why is no real title available?)
• scientific article; zbMATH DE number 1142293 (Why is no real title available?)
• Iterated GSMs and CO-CFL
• Logical basis for information theory and probability theory
• On the Length of Programs for Computing Finite Binary Sequences

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6183604)