|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc050306,
author = {Shallit, Jeffrey},
title = {Automaticity and Rationality},
journal = jalc,
year = 2000,
volume = 5,
number = 3,
pages = {255--268},
keywords = {regular language, finite automata, formal power series,
rational series, linear complexity, linear span, linear
recurrence, linear feedback shift register sequence,
automaticity, rationality, continued fraction},
abstract = {Automaticity is a measure of descriptional complexity for
formal languages $L$, and measures how closely $L$ can be
approximated by regular languages. I survey some of the known
results and open problems on automaticity. I also discuss a
measure which I call ``rationality'', and explain how it
generalizes the well-known concept of linear complexity.}
}