STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY

被引：3

作者：

Calude, Cristian S. ^{[1
]}

Salomaa, Kai ^{[2
]}

Roblot, Tania K. ^{[1
]}

机构：

[1] Univ Auckland, Dept Comp Sci, Auckland 1, New Zealand

[2] Queens Univ, Sch Comp, Kingston, ON, Canada

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2012年 / 23卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Finite transducers; descriptional complexity; state-size hierarchy; computability; COMPRESSION; ALGORITHMS; DIMENSION;

D O I：

10.1142/S0129054112400035

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the number of states needed for transducers used in minimal descriptions of arbitrary strings and, as our main result, show that the state-size hierarchy with respect to a standard encoding is infinite. We consider corresponding hierarchies yielded by more general computable encodings and establish that for a suitably chosen computable encoding every level of the state-size hierarchy can be strict.

引用

页码：37 / 50

页数：14

共 18 条

[1] Allouche J.P., 2003, Automatic sequences: Theory, applications, generalizations
[2] [Anonymous], 1979, Transductions and context-free languages
[3] Entropy rates and finite-state dimension
Bourke, C
Hitchcock, JM
Vinodchandran, NV
[J]. THEORETICAL COMPUTER SCIENCE, 2005, 349 (03) : 392 - 406
[4] Buhrman H, 1997, LECT NOTES COMPUT SC, V1200, P105, DOI 10.1007/BFb0023452
[5] Calude C.S., 2002, INFORM RONDOMMESS AL
[6] Calude C.S., 2010, PROGRAMS PROOFS, P73
[7] Chaitin G., 1987, Algorithmic Information Theory
[8] Charikar M., 2002, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, P792, DOI [DOI 10.1145/509907.510021, 10.1145]
[9] Finite-state dimension and real arithmetic
Doty, David
Lutz, Jack H.
Nandakumar, Satyadev
[J]. INFORMATION AND COMPUTATION, 2007, 205 (11) : 1640 - 1651
[10] GUY R. K., 2004, Unsolved Problems in Number Theory

← 1 2 →