Comparing descriptional and computational complexity of infinite words

DOI10.1007/3-540-58131-6_46zbMATH Open1529.68118OpenAlexW2115348183MaRDI QIDQ6183604FDOQ6183604

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

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

Mathematics Subject Classification ID

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

Cites Work

• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part I
• Logical basis for information theory and probability theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• Iterated GSMs and CO-CFL

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)