Finite State Incompressible Infinite Sequences

DOI10.1007/978-3-319-06089-7_5MaRDI QIDQ5410635zbMATH OpenOpenAlexFDO

Authors Ludwig Staiger, Cristian S. Calude, Frank Stephan

Publication date 16 April 2014

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

Full work available at URL https://doi.org/10.1007/978-3-319-06089-7_5

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• Finite state incompressible infinite sequences
• Compressibility of Deterministic and Random Infinite Sequences
• scientific article; zbMATH DE number 1048038
• Finite-state automata on infinite inputs
• Non-stochastic infinite and finite sequences
• Finite-state independence and normal sequences
• On the complexity of infinite sequences
• On finite representations of infinite-state behaviours
• On finite representations of infinite sequences of terms
• Long finite sequences

Cited in

(11)

• An unpredictability approach to finite-state randomness
• Automatic Kolmogorov complexity and normality revisited
• Finite-state independence and normal sequences
• Finite state incompressible infinite sequences
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
• State-size hierarchy for finite-state complexity
• Finite-state complexity and the size of transducers
• Finite-state genericity. On the diagonalization strength of finite automata.
• Finite state complexity
• Finite automata and randomness
• On normality in shifts of finite type

This page was built for publication: Finite State Incompressible Infinite Sequences

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