Document Open Access Logo

Definable Operations On Weakly Recognizable Sets of Trees

Authors Jacques Duparc, Alessandro Facchini, Filip Murlak

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2011.363.pdf
  • Filesize: 0.59 MB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • alternating automata
  • Wadge hierarchy
  • index hierarchy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge degree of a given automaton is computable. The weak index and the Borel rank coincide, and are computable. An equivalent automaton of minimal index can be computed in polynomial time (if the productive states of the automaton are given).

Cite As Get BibTex

Jacques Duparc, Alessandro Facchini, and Filip Murlak. Definable Operations On Weakly Recognizable Sets of Trees. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 363-374, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011) https://doi.org/10.4230/LIPIcs.FSTTCS.2011.363

Author Details

Jacques Duparc
Alessandro Facchini
Filip Murlak
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact