Back to Search
Start Over
Finite state complexity
- Source :
-
Theoretical Computer Science . Sep2011, Vol. 412 Issue 41, p5668-5677. 10p. - Publication Year :
- 2011
-
Abstract
- Abstract: In this paper we develop a version of Algorithmic Information Theory (AIT) based on finite transducers instead of Turing machines; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 41
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 65046707
- Full Text :
- https://doi.org/10.1016/j.tcs.2011.06.021