Synchronized rational relations of finite and infinite words (Q685453)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Synchronized rational relations of finite and infinite words |
scientific article |
Statements
Synchronized rational relations of finite and infinite words (English)
0 references
17 October 1993
0 references
Rational relations on finite and infinite words are considered. The emphasis is on the synchronized (letter-to-letter) rational relations and the rational relations that are computed by automata with bounded delay. The authors make use of the resynchronization lemma of Eilenberg and Schützenberger. This result is generalized for infinite words. For the finite words it is shown that the synchronized rational relations are deterministic rational relations. Moreover, it is shown that it is undecidable whether a rational relation is synchronized or not. For infinite words it is proved that the family of deterministic synchronized rational relations is the intersection of the families of synchronized rational relations and deterministic rational relations.
0 references
free monoids
0 references
synchronization
0 references
rational relations
0 references