STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY

DOI10.1142/S0129054112400035zbMath1283.68191DBLPjournals/ijfcs/CaludeSR12OpenAlexW2097880459WikidataQ57001511 ScholiaQ57001511MaRDI QIDQ2909179

Tania K. Roblot, Kai Salomaa, 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

computabilitydescriptional complexityfinite transducersstate-size hierarchy

Mathematics Subject Classification ID

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

Related Items (2)

State Complexity of Kleene-Star Operations on Trees ⋮ Finite state incompressible infinite sequences

Cites Work

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

This page was built for publication: STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY