Continuity of functional transducers: a profinite study of rational functions

Cadilhac, Michaël; Carton, Olivier; Paperman, Charles

Type de document :

Article dans une revue scientifique

DOI :

10.23638/LMCS-16(1:24)2020

URL permanente :

http://hdl.handle.net/20.500.12210/57145

Titre :

Continuity of functional transducers: a profinite study of rational functions

Auteur(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]

Titre de la revue :

Logical Methods in Computer Science

Éditeur :

Logical Methods in Computer Science Association

Date de publication :

2020-02-21

Mot(s)-clé(s) en anglais :

Transducers
rational functions
language varieties
continuity

Discipline(s) HAL :

Informatique [cs]/Théorie et langage formel [cs.FL]

Résumé en anglais : [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 ...
Lire la suite >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?Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

DÉfis pour la Logique, les Transducteurs et les Automates

Collections :