6533b833fe1ef96bd129c1a3
RESEARCH PRODUCT
Sur les Codes ZigZag et Leur Décidabilité
M. Anselmosubject
Philosophy of languageCombinatoricsSet (abstract data type)Discrete mathematicsGeneral Computer ScienceRegular languageZigzagType (model theory)Computer Science(all)Theoretical Computer ScienceMathematicsDecidabilityAutomatondescription
AbstractThis paper deals with zigzag factorizations and zigzag codes. The language of “zigzag” over a regular language is represented by constructing a special family of two-way automata. Decidability of zigzag codes, previously shown for the finite languages, is proved here for all regular languages by the analysis of the set of “crossing sequences” produced by a two-way automation in the family. We also obtain that it is decidable whether or not a two-way automation of a certain type is non-ambiguous.RésuméDans ce papier on reprend les notions de factorisation zigzag et de code zigzag. On construit pour tout langage rationnel, une famille d'automates bilatéres lesquels reconnaissent les mots obtenus “par zigzag” sur le langage. La décidabilité des codes zigzag, qui avait été prouvée pour les langages finis, est démontrée ici pour tout langage rationnel, en analysant les “suites de traversée” (crossing sequences) engendrées par un automate bilatère de la famille. Une conséquence est la décidabilité de la non-ambiguité des automates bilatères d'un certain type.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1990-08-01 |