Continuity of functional transducers: a ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
Continuity of functional transducers: a profinite study of rational functions
Author(s) :
Cadilhac, Michaël [Auteur]
DePaul University [Chicago]
Carton, Olivier [Auteur]
Institut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
DePaul University [Chicago]
Carton, Olivier [Auteur]
Institut de Recherche en Informatique Fondamentale [IRIF (UMR_8243)]
Paperman, Charles [Auteur]
Linking Dynamic Data [LINKS]
Journal title :
Logical Methods in Computer Science
Publisher :
Logical Methods in Computer Science Association
Publication date :
2020-02-21
English keyword(s) :
Transducers
rational functions
language varieties
continuity
rational functions
language varieties
continuity
HAL domain(s) :
Informatique [cs]/Théorie et langage formel [cs.FL]
English abstract : [en]
A word-to-word function is continuous for a class of languages V if its inverse maps V-languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the ...
Show more >A word-to-word function is continuous for a class of languages V if its inverse maps V-languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes. Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages. To this end, we develop a robust theory rooted in the standard profinite analysis of regular languages. Since previous algebraic studies of transducers have focused on the sole structure of the underlying input automaton, we also compare the two algebraic approaches. We focus on two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?Show less >
Show more >A word-to-word function is continuous for a class of languages V if its inverse maps V-languages to V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes. Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages. To this end, we develop a robust theory rooted in the standard profinite analysis of regular languages. Since previous algebraic studies of transducers have focused on the sole structure of the underlying input automaton, we also compare the two algebraic approaches. We focus on two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-03111682/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03111682/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03111682/document
- Open access
- Access the document
- document
- Open access
- Access the document
- transducer.pdf
- Open access
- Access the document