Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
On a Class of Bijective Binary Transducers with Finitary Description Despite Infinite State Set
verfasst von : Michael Vielhaber, Mónica del Pilar Canales Ch.
Erschienen in: Implementation and Application of Automata
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that an infinite isometry
f
on {0,1}
ω
,
i.e.
computable by an infinite transducer
T
f
, can be represented finitarily, provided the isometry [
σ
,
f
] :=
σ
− 1
∘
f
− 1
∘
σ
∘
f
, the shift commutator of
f
, is finite,
i.e.
has a finite transducer
T
[
σ
,
f
]
. We can describe all states of
T
f
as words over
Q
[
σ
,
f
]
and, using the nextstate and output functions of
T
[
σ
,
f
]
, obtain linear time algorithms for
T
f
(in the length of the word in
$Q^*_{[ \sigma,f ]}$
describing the state in
Q
f
). The task of determining state equivalence within the first
n
input symbols or
N
=2
n
+ 1
-1 states is
polynomial
in the number
N
of states, if the shift commutator is finite.