5 Search Results for "Arnold, Andr�"


Document
A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation

Authors: André Arnold, Damian Niwiński, and Paweł Parys

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)


Abstract
We consider nested fixed-point expressions like μ z. ν y. μ x. f(x,y,z) evaluated over a finite lattice, and ask how many queries to a function f are needed to find the value. The previous upper bounds for a monotone function f of arity d over the lattice {0,1}ⁿ were of the order n^{𝒪(d)}, whereas a lower bound of Ω(n²/(lg n)) is known in case when at least one alternation between the least (μ) and the greatest (ν) fixed point occurs in the expression. Following a recent development for parity games, we show here that a quasi-polynomial number of queries is sufficient, namely n^{lg(d/lg n)+𝒪(1)}. The algorithm is an abstract version of several algorithms proposed recently by a number of authors, which involve (implicitly or explicitly) the structure of a universal tree. We then show a quasi-polynomial lower bound for the number of queries used by the algorithms in consideration.

Cite as

André Arnold, Damian Niwiński, and Paweł Parys. A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{arnold_et_al:LIPIcs.CSL.2021.9,
  author =	{Arnold, Andr\'{e} and Niwi\'{n}ski, Damian and Parys, Pawe{\l}},
  title =	{{A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.9},
  URN =		{urn:nbn:de:0030-drops-134430},
  doi =		{10.4230/LIPIcs.CSL.2021.9},
  annote =	{Keywords: Mu-calculus, Parity games, Quasi-polynomial time, Black-box algorithm}
}
Document
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
Using Affective Technologies to Increase Engagement and Motivation in Fitness and Sports

Authors: Elisabeth André

Published in: Dagstuhl Seminar Proceedings, Volume 8372, Computer Science in Sport - Mission and Methods (2008)


Abstract
Work by Picard and others has created considerable awareness for the role of affect in human-computer interaction. In fact, a strong new field is emerging in computer science: affective computing. In my presentation, I presented first ideas to make use of affective technologies in fitness and sports.

Cite as

Elisabeth André. Using Affective Technologies to Increase Engagement and Motivation in Fitness and Sports. In Computer Science in Sport - Mission and Methods. Dagstuhl Seminar Proceedings, Volume 8372, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{andre:DagSemProc.08372.9,
  author =	{Andr\'{e}, Elisabeth},
  title =	{{Using Affective Technologies to Increase Engagement and Motivation in Fitness and Sports}},
  booktitle =	{Computer Science in Sport - Mission and Methods},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8372},
  editor =	{Arnold Baca and Martin Lames and Keith Lyons and Bernhard Nebel and Josef Wiemeyer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08372.9},
  URN =		{urn:nbn:de:0030-drops-16842},
  doi =		{10.4230/DagSemProc.08372.9},
  annote =	{Keywords: Affective computing}
}
Document
Algorithms in Automata Theory (Dagstuhl Seminar 9406)

Authors: André Arnold, Helmut Seidl, and Bernhard Steffen

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

André Arnold, Helmut Seidl, and Bernhard Steffen. Algorithms in Automata Theory (Dagstuhl Seminar 9406). Dagstuhl Seminar Report 81, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)


Copy BibTex To Clipboard

@TechReport{arnold_et_al:DagSemRep.81,
  author =	{Arnold, Andr\'{e} and Seidl, Helmut and Steffen, Bernhard},
  title =	{{Algorithms in Automata Theory (Dagstuhl Seminar 9406)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{81},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.81},
  URN =		{urn:nbn:de:0030-drops-149691},
  doi =		{10.4230/DagSemRep.81},
}
Document
Automata Theory: Distributed Models (Dagstuhl Seminar 9302)

Authors: André Arnold, Lutz Priese, and Roland Vollmer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

André Arnold, Lutz Priese, and Roland Vollmer. Automata Theory: Distributed Models (Dagstuhl Seminar 9302). Dagstuhl Seminar Report 54, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1993)


Copy BibTex To Clipboard

@TechReport{arnold_et_al:DagSemRep.54,
  author =	{Arnold, Andr\'{e} and Priese, Lutz and Vollmer, Roland},
  title =	{{Automata Theory: Distributed Models (Dagstuhl Seminar 9302)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1993},
  type = 	{Dagstuhl Seminar Report},
  number =	{54},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.54},
  URN =		{urn:nbn:de:0030-drops-149422},
  doi =		{10.4230/DagSemRep.54},
}
  • Refine by Author
  • 4 Arnold, André
  • 1 André, Elisabeth
  • 1 Michalewski, Henryk
  • 1 Niwinski, Damian
  • 1 Niwiński, Damian
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 1 Affective computing
  • 1 Alternating automata on infinite trees
  • 1 Black-box algorithm
  • 1 Index hierarchy
  • 1 Mu-calculus
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 1993
  • 1 1994
  • 1 2008
  • 1 2012
  • 1 2021

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