3 Search Results for "Hummel, Szczepan"

Document
DOI: 10.4230/LIPIcs.CSL.2015.534
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.}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.396
On the separation question for tree languages

Authors: André Arnold, Henryk Michalewski, and Damian Niwinski

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We show that the separation property fails for the classes Sigma_n of the Rabin-Mostowski index hierarchy of alternating automata on infinite trees. This extends our previous result (obtained with Szczepan Hummel) on the failure of the separation property for the class Sigma_2 (i.e., for co-Buchi sets). It remains open whether the separation property does hold for the classes Pi_n of the index hierarchy. To prove our result, we first consider the Rabin-Mostowski index hierarchy of deterministic automata on infinite words, for which we give a complete answer (generalizing previous results of Selivanov): the separation property holds for Pi_n and fails for Sigma_n-classes. The construction invented for words turns out to be useful for trees via a suitable game.
Cite as

André Arnold, Henryk Michalewski, and Damian Niwinski. On the separation question for tree languages. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 396-407, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{arnold_et_al:LIPIcs.STACS.2012.396,
  author =	{Arnold, Andr\'{e} and Michalewski, Henryk and Niwinski, Damian},
  title =	{{On the separation question for tree languages}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{396--407},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.396},
  URN =		{urn:nbn:de:0030-drops-34156},
  doi =		{10.4230/LIPIcs.STACS.2012.396},
  annote =	{Keywords: Alternating automata on infinite trees, Index hierarchy, Separation property}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1849
On the Borel Inseparability of Game Tree Languages

Authors: Szczepan Hummel, Henryk Michalewski, and Damian Niwinski

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The game tree languages can be viewed as an automata-theoretic counterpart of parity games on graphs. They witness the strictness of the index hierarchy of alternating tree automata, as well as the fixed-point hierarchy over binary trees. We consider a game tree language of the first non-trivial level, where Eve can force that 0 repeats from some moment on, and its dual, where Adam can force that 1 repeats from some moment on. Both these sets (which amount to one up to an obvious renaming) are complete in the class of co-analytic sets. We show that they cannot be separated by any Borel set, hence {\em a fortiori\/} by any weakly definable set of trees. This settles a case left open by L. Santocanale and A. Arnold, who have thoroughly investigated the separation property within the $\mu $-calculus and the automata index hierarchies. They showed that separability fails in general for non-deterministic automata of type $\Sigma^{\mu }_{n} $, starting from level $n=3$, while our result settles the missing case $n=2$.
Cite as

Szczepan Hummel, Henryk Michalewski, and Damian Niwinski. On the Borel Inseparability of Game Tree Languages. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 565-576, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hummel_et_al:LIPIcs.STACS.2009.1849,
  author =	{Hummel, Szczepan and Michalewski, Henryk and Niwinski, Damian},
  title =	{{On the Borel Inseparability of Game Tree Languages}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{565--576},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1849},
  URN =		{urn:nbn:de:0030-drops-18493},
  doi =		{10.4230/LIPIcs.STACS.2009.1849},
  annote =	{Keywords: Tree automata, Separation property, Borel sets, Parity games}
}
  • Refine by Author
  • 2 Hummel, Szczepan
  • 2 Michalewski, Henryk
  • 2 Niwinski, Damian
  • 1 Arnold, André
  • 1 Duparc, Jacques
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Separation property
  • 1 Alternating automata on infinite trees
  • 1 Borel sets
  • 1 Index hierarchy
  • 1 Parity games
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2009
  • 1 2012
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact