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
Secondary volumes: Special Issue in Memory of Zoltán Ésik
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 3505 times.
This article's PDF has been downloaded 744 times.