Cristian Calude (University of Auckland) |
Kai Salomaa (Queen's University) |
Tania Roblot (University of Auckland) |
Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the state-size of transducers needed for minimal descriptions of arbitrary strings and, as our main result, we show that the state-size hierarchy with respect to a standard encoding is infinite. We consider also hierarchies yielded by more general computable encodings. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.31.6 | bibtex | |
Comments and questions to:
![]() |
For website issues:
![]() |