State-size hierarchy for finite-state complexity

DOI10.1142/S0129054112400035MaRDI QIDQ2909179zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kai Salomaa, Tania K. Roblot, Cristian S. Calude

Publication date 30 August 2012

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054112400035

zbMATH Keywords

descriptional complexitycomputabilityfinite transducersstate-size hierarchy

Mathematics Subject Classification ID

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

Recommendations

• Finite-state complexity and the size of transducers
• Finite state complexity
• Finite state incompressible infinite sequences
• Finite State Incompressible Infinite Sequences
• Invariance and Universality of Complexity

Cites work

• Algorithmic Information Theory
• Automatic Sequences
• Automaticity. I: Properties of a measure of descriptional complexity
• Entropy rates and finite-state dimension

Cited in

(8)

• State-complexity of finite-state devices, state compressibility and incompressibility
• Finite state incompressible infinite sequences
• Finite state complexity
• Algorithmic information theory and computational complexity
• State complexity of Kleene-star operations on trees
• State-complexity hierarchies of uniform languages of alphabet-size length
• Finite-state complexity and the size of transducers
• scientific article; zbMATH DE number 7301304 (Why is no real title available?)

This page was built for publication: State-size hierarchy for finite-state complexity

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