1 Search Results for "Fournier, Kevin"


Document
On Unambiguous Regular Tree Languages of Index (0,2)

Authors: Jacques Duparc, Kevin Fournier, and Szczepan Hummel

Published in: LIPIcs, Volume 41, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)


Abstract
Unambiguous automata are usually seen as a natural class of automata in-between deterministic and nondeterministic ones. We show that in case of infinite tree languages, the unambiguous ones are topologically far more complicated than the deterministic ones. We do so by providing operations that generate a family (A_{alpha})_{alpha < phi_2(0)} of unambiguous automata such that: 1. It respects the strict Wadge ordering: alpha < beta if and only if A_{alpha} <_W A_{beta}. This can be established without the help of any determinacy principle, simply by providing effective winning strategies in the underlying games. 2. Its length (phi_2(0)) is the first fixpoint of the ordinal function that itself enumerates all fixpoints of the ordinal exponentiation x |-> omega^x: an ordinal tremendously larger than (omega^(omega))^3 +3 which is the height of the Wadge hierarchy of deterministic tree languages as uncovered by Filip Murlak. 3. The priorities of all these parity automata only range from 0 to 2.

Cite as

Jacques Duparc, Kevin Fournier, and Szczepan Hummel. On Unambiguous Regular Tree Languages of Index (0,2). In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 534-548, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{duparc_et_al:LIPIcs.CSL.2015.534,
  author =	{Duparc, Jacques and Fournier, Kevin and Hummel, Szczepan},
  title =	{{On Unambiguous Regular Tree Languages of Index (0,2)}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{534--548},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Kreutzer, Stephan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2015.534},
  URN =		{urn:nbn:de:0030-drops-54369},
  doi =		{10.4230/LIPIcs.CSL.2015.534},
  annote =	{Keywords: Tree Automata, Unambiguity, Wadge Hierarchy.}
}
  • Refine by Author
  • 1 Duparc, Jacques
  • 1 Fournier, Kevin
  • 1 Hummel, Szczepan

  • Refine by Classification

  • Refine by Keyword
  • 1 Tree Automata
  • 1 Unambiguity
  • 1 Wadge Hierarchy.

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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