Emmanuel Filiot ; Olivier Gauwin ; Nathan Lhote - Logical and Algebraic Characterizations of Rational Transductions

lmcs:3653 - Logical Methods in Computer Science, December 19, 2019, Volume 15, Issue 4 - https://doi.org/10.23638/LMCS-15(4:16)2019
Logical and Algebraic Characterizations of Rational TransductionsArticle

Authors: Emmanuel Filiot ; Olivier Gauwin ; Nathan Lhote

    Rational word languages can be defined by several equivalent means: finite state automata, rational expressions, finite congruences, or monadic second-order (MSO) logic. The robust subclass of aperiodic languages is defined by: counter-free automata, star-free expressions, aperiodic (finite) congruences, or first-order (FO) logic. In particular, their algebraic characterization by aperiodic congruences allows to decide whether a regular language is aperiodic. We lift this decidability result to rational transductions, i.e., word-to-word functions defined by finite state transducers. In this context, logical and algebraic characterizations have also been proposed. Our main result is that one can decide if a rational transduction (given as a transducer) is in a given decidable congruence class. We also establish a transfer result from logic-algebra equivalences over languages to equivalences over transductions. As a consequence, it is decidable if a rational transduction is first-order definable, and we show that this problem is PSPACE-complete.


    Volume: Volume 15, Issue 4
    Published on: December 19, 2019
    Accepted on: October 16, 2019
    Submitted on: May 11, 2017
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Extensions of Stream Processing; Funder: French National Research Agency (ANR); Code: ANR-13-JS02-0010

    Consultation statistics

    This page has been seen 981 times.
    This article's PDF has been downloaded 300 times.