Finite state complexity
From MaRDI portal
Publication:719308
DOI10.1016/J.TCS.2011.06.021zbMath1235.68088OpenAlexW2083810917WikidataQ57001526 ScholiaQ57001526MaRDI QIDQ719308
Kai Salomaa, Tania K. Roblot, Cristian S. Calude
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.021
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (8)
Invariance and Universality of Complexity ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Pushdown and Lempel-Ziv depth ⋮ A circuit complexity formulation of algorithmic information theory ⋮ On the Difference Between Finite-State and Pushdown Depth ⋮ Nondeterministic automatic complexity of overlap-free and almost square-free words ⋮ Finite state incompressible infinite sequences
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Representation of left-computable \(\varepsilon \)-random reals
- Entropy rates and finite-state dimension
- Tight lower bounds on the length of word chains
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Automaticity. I: Properties of a measure of descriptional complexity
- Simulating finite automata with context-free grammars.
- Endliche Automaten und Zufallsfolgen
- Algorithmic Randomness and Complexity
- Approximating the smallest grammar
- Algorithmic Information Theory
- Compression of individual sequences via variable-rate coding
- Resource-bounded kolmogorov complexity revisited
- Feasible Depth
- Theory and Applications of Models of Computation
This page was built for publication: Finite state complexity
