|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040303,
author = {Devolder, Jeanne},
title = {Generators with Bounded Deciphering Delay for Rational
$\omega$-Languages},
journal = jalc,
year = 1999,
volume = 4,
number = 3,
pages = {183--204},
keywords = {Infinite words, $\omega$-generator, rational language,
code with bounded deciphering delay},
abstract = {Given a rational $\omega$-language $L$, we are interested
in the study of some particular generators (i.\,e.\ the
languages $G$ for which $G^{\omega}=L$). The most interesting
generators of $L$ are those which are $\omega$-codes. It is
known that one can decide whether a rational
$\omega$-language exhibits prefix-free generators, but the
question remains open for $\omega$-codes and for codes with
bounded deciphering delay. To unravel this last question, we
define here languages with bounded deciphering delay, i.\,e.\
languages allowing to perform the decoding of infinite words
after some bounded delay, without waiting the whole message.
But, contrary to codes with bounded deciphering delay, these
languages do not ensure a single deciphering. We show that
it is possible to decide whether a rational
$\omega$-language exhibits such generators. This allows to
derive a few necessary or sufficient conditions for the
existence of generators which are codes with bounded
deciphering delay.}
}