Michaël Cadilhac ; Olivier Carton ; Charles Paperman - Continuity of Functional Transducers: A Profinite Study of Rational Functions

lmcs:4336 - Logical Methods in Computer Science, February 21, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:24)2020
Continuity of Functional Transducers: A Profinite Study of Rational FunctionsArticle

Authors: Michaël Cadilhac ; Olivier Carton ; Charles Paperman

A word-to-word function is continuous for a class of languages~$\mathcal{V}$ if its inverse maps $\mathcal{V}$_languages to~$\mathcal{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?


Volume: Volume 16, Issue 1
Secondary volumes: Selected Papers of the 44th International Colloquium on Automata, Languages and Programming (ICALP 2017) - Track B
Published on: February 21, 2020
Accepted on: December 16, 2019
Submitted on: March 1, 2018
Keywords: Formal Languages and Automata Theory, Logic in Computer Science
Funding:
    Source : OpenAIRE Graph
  • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

Consultation statistics

This page has been seen 2179 times.
This article's PDF has been downloaded 461 times.