Olivier Carton ; Dominique Perrin ; Jean-Éric Pin - A survey on difference hierarchies of regular languages

lmcs:3161 - Logical Methods in Computer Science, March 29, 2018, Volume 14, Issue 1 - https://doi.org/10.23638/LMCS-14(1:24)2018
A survey on difference hierarchies of regular languagesArticle

Authors: Olivier Carton ; Dominique Perrin ; Jean-Éric Pin

    Difference hierarchies were originally introduced by Hausdorff and they play an important role in descriptive set theory. In this survey paper, we study difference hierarchies of regular languages. The first sections describe standard techniques on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques by giving decidability results on the difference hierarchies based on shuffle ideals, strongly cyclic regular languages and the polynomial closure of group languages.

    https://doi.org/10.23638/LMCS-14(1:24)2018
    Source: arXiv.org:1702.08023
    Volume: Volume 14, Issue 1
    Published on: March 29, 2018
    Accepted on: March 8, 2018
    Submitted on: February 28, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory,68Q70, 68Q45, 20M35
    Licence: Attribution 4.0 International (CC BY 4.0)
    Funding:
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007
    • Duality in Formal Languages and Logic - a unifying approach to complexity and semantics; Funder: European Commission; Code: 670624

    Share and export

    Consultation statistics

    This page has been seen 1973 times.
    This article's PDF has been downloaded 460 times.