9 Search Results for "Neumann, L�szl�"


Document
Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set

Authors: Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.

Cite as

Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{dcosta_et_al:LIPIcs.MFCS.2022.39,
  author =	{D'Costa, Julian and Lefaucheux, Engel and Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.39},
  URN =		{urn:nbn:de:0030-drops-168374},
  doi =		{10.4230/LIPIcs.MFCS.2022.39},
  annote =	{Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Uniform termination bounds}
}
Document
Track A: Algorithms, Complexity and Games
Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)

Authors: Paweł Gawrychowski and Karol Pokorski

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We revisit the complexity of the classical Interval Scheduling in the dynamic setting. In this problem, the goal is to maintain a set of intervals under insertions and deletions and report the size of the maximum size subset of pairwise disjoint intervals after each update. Nontrivial approximation algorithms are known for this problem, for both the unweighted and weighted versions [Henzinger, Neumann, Wiese, SoCG 2020]. Surprisingly, it was not known if the general exact version admits an exact solution working in sublinear time, that is, without recomputing the answer after each update. Our first contribution is a structure for Dynamic Interval Scheduling with amortized 𝒪̃(n^{1/3}) update time. Then, building on the ideas used for the case of one machine, we design a sublinear solution for any constant number of machines: we describe a structure for Dynamic Interval Scheduling on m ≥ 2 machines with amortized 𝒪̃(n^{1 - 1/m}) update time. We complement the above results by considering Dynamic Weighted Interval Scheduling on one machine, that is maintaining (the weight of) the maximum weight subset of pairwise disjoint intervals. We show an almost linear lower bound (conditioned on the hardness of Minimum Weight k-Clique) for the update/query time of any structure for this problem. Hence, in the weighted case one should indeed seek approximate solutions.

Cite as

Paweł Gawrychowski and Karol Pokorski. Sublinear Dynamic Interval Scheduling (On One or Multiple Machines). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.ICALP.2022.67,
  author =	{Gawrychowski, Pawe{\l} and Pokorski, Karol},
  title =	{{Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.67},
  URN =		{urn:nbn:de:0030-drops-164086},
  doi =		{10.4230/LIPIcs.ICALP.2022.67},
  annote =	{Keywords: interval scheduling, dynamic problems, data structures, greedy algorithms}
}
Document
On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets

Authors: Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We study the computational complexity of the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets, or equivalently the Termination Problem for affine loops with compact semialgebraic guard sets. Consider the fragment of the theory of the reals consisting of negation-free ∃ ∀-sentences without strict inequalities. We derive several equivalent characterisations of the associated complexity class which demonstrate its robustness and illustrate its expressive power. We show that the Compact Escape Problem is complete for this class.

Cite as

Julian D'Costa, Engel Lefaucheux, Eike Neumann, Joël Ouaknine, and James Worrell. On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{dcosta_et_al:LIPIcs.MFCS.2021.33,
  author =	{D'Costa, Julian and Lefaucheux, Engel and Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.33},
  URN =		{urn:nbn:de:0030-drops-144734},
  doi =		{10.4230/LIPIcs.MFCS.2021.33},
  annote =	{Keywords: Discrete linear dynamical systems, Program termination, Compact semialgebraic sets, Theory of the reals}
}
Document
Track A: Algorithms, Complexity and Games
Decision Problems for Second-Order Holonomic Recurrences

Authors: Eike Neumann, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n) f(n + 1) + Q(n) f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f(1), f(2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones.

Cite as

Eike Neumann, Joël Ouaknine, and James Worrell. Decision Problems for Second-Order Holonomic Recurrences. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 99:1-99:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{neumann_et_al:LIPIcs.ICALP.2021.99,
  author =	{Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{Decision Problems for Second-Order Holonomic Recurrences}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{99:1--99:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.99},
  URN =		{urn:nbn:de:0030-drops-141682},
  doi =		{10.4230/LIPIcs.ICALP.2021.99},
  annote =	{Keywords: holonomic sequences, Positivity Problem, Skolem Problem}
}
Document
On Ranking Function Synthesis and Termination for Polynomial Programs

Authors: Eike Neumann, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)


Abstract
We consider the problem of synthesising polynomial ranking functions for single-path loops over the reals with continuous semi-algebraic update function and compact semi-algebraic guard set. We show that a loop of this form has a polynomial ranking function if and only if it terminates. We further show that termination is decidable for such loops in the special case where the update function is affine.

Cite as

Eike Neumann, Joël Ouaknine, and James Worrell. On Ranking Function Synthesis and Termination for Polynomial Programs. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{neumann_et_al:LIPIcs.CONCUR.2020.15,
  author =	{Neumann, Eike and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{On Ranking Function Synthesis and Termination for Polynomial Programs}},
  booktitle =	{31st International Conference on Concurrency Theory (CONCUR 2020)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-160-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{171},
  editor =	{Konnov, Igor and Kov\'{a}cs, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.15},
  URN =		{urn:nbn:de:0030-drops-128278},
  doi =		{10.4230/LIPIcs.CONCUR.2020.15},
  annote =	{Keywords: Semi-algebraic sets, Polynomial ranking functions, Polynomial programs}
}
Document
APPROX
Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues

Authors: Gary L. Miller, Noel J. Walkington, and Alex L. Wang

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
We present two graph quantities Psi(G,S) and Psi_2(G) which give constant factor estimates to the Dirichlet and Neumann eigenvalues, lambda(G,S) and lambda_2(G), respectively. Our techniques make use of a discrete Hardy-type inequality due to Muckenhoupt.

Cite as

Gary L. Miller, Noel J. Walkington, and Alex L. Wang. Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{miller_et_al:LIPIcs.APPROX-RANDOM.2019.8,
  author =	{Miller, Gary L. and Walkington, Noel J. and Wang, Alex L.},
  title =	{{Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.8},
  URN =		{urn:nbn:de:0030-drops-112236},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.8},
  annote =	{Keywords: Hardy, Muckenhoupt, Laplacian, eigenvalue, effective resistance}
}
Document
GerManC - Towards a Methodology for Constructing and Annotating Historical Corpora

Authors: Astrid Ensslin, Martin Durrell, and Paul Bennett

Published in: Dagstuhl Seminar Proceedings, Volume 6491, Digital Historical Corpora- Architecture, Annotation, and Retrieval (2007)


Abstract
Our paper focuses on the one hand on the challenges posed by the structural variability, flexibility and ambiguity found in historical corpora and evaluates methods of dealing with them on the other. We are currently engaged in a project which aims to compile a representative corpus of German for the period 1650-1800. Looking at exemplary data from the first stage of this project (1650-1700), which consists of newspaper texts from this period, we first aim from the perspective of corpus linguistics to identify the problems associated with the morphological, syntactical and graphemic peculiarities that are characteristic of that particular stage. Specific phenomena which significantly complicate automatic tagging, lemmatisation and parsing include, for instance, "abperlende" (Admoni 1980; Demske-Neumann 1990), i.e. complex and often asyndetic syntax; non-syntactic, prosodic, virgulated punctuation (Demske et al. 2004; cf. Stolt 1990), inflectional variability (e.g. Admoni 1990; Besch & Wegera 1987), as well as partly unsystematic and almost experimental allomorphic and allographic (Kettmann, 1992) diversity. Secondly, we outline a methodology which is intended to facilitate the construction and annotation of such corpora which antedate linguistic standardisation. This is informed by "conventional" and innovative tagging techniques and tools, which are evaluated in terms of utility and accuracy. Finally, we attempt to evaluate the degree to which annotation tools for specialist corpora of this kind can be developed which will substitute for manual or semi-automated annotation.

Cite as

Astrid Ensslin, Martin Durrell, and Paul Bennett. GerManC - Towards a Methodology for Constructing and Annotating Historical Corpora. In Digital Historical Corpora- Architecture, Annotation, and Retrieval. Dagstuhl Seminar Proceedings, Volume 6491, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{ensslin_et_al:DagSemProc.06491.7,
  author =	{Ensslin, Astrid and Durrell, Martin and Bennett, Paul},
  title =	{{GerManC - Towards a Methodology for Constructing and Annotating Historical Corpora}},
  booktitle =	{Digital Historical Corpora- Architecture, Annotation, and Retrieval},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6491},
  editor =	{Lou Burnard and Milena Dobreva and Norbert Fuhr and Anke L\"{u}deling},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06491.7},
  URN =		{urn:nbn:de:0030-drops-10467},
  doi =		{10.4230/DagSemProc.06491.7},
  annote =	{Keywords: Early Modern German; newspaper corpus; GerManC; variation; annotation; tagging}
}
Document
06221 Abstracts Collection – Computational Aestethics in Graphics, Visualization and Imaging

Authors: Bruce Gooch, László Neumann, Werner Purgathofer, and Mateu Sbert

Published in: Dagstuhl Seminar Proceedings, Volume 6221, Computational Aesthetics in Graphics, Visualization and Imaging (2007)


Abstract
From 28.05.06 to 02.06.06, the Dagstuhl Seminar 06221 ``Computational Aesthetics in Graphics, Visualization and Imaging'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Bruce Gooch, László Neumann, Werner Purgathofer, and Mateu Sbert. 06221 Abstracts Collection – Computational Aestethics in Graphics, Visualization and Imaging. In Computational Aesthetics in Graphics, Visualization and Imaging. Dagstuhl Seminar Proceedings, Volume 6221, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{gooch_et_al:DagSemProc.06221.1,
  author =	{Gooch, Bruce and Neumann, L\'{a}szl\'{o} and Purgathofer, Werner and Sbert, Mateu},
  title =	{{06221 Abstracts Collection – Computational Aestethics in Graphics, Visualization and Imaging}},
  booktitle =	{Computational Aesthetics in Graphics, Visualization and Imaging},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6221},
  editor =	{Bruce Gooch and L\'{a}szl\'{o} Neumann and Werner Purgathofer and Mateu Sbert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06221.1},
  URN =		{urn:nbn:de:0030-drops-8756},
  doi =		{10.4230/DagSemProc.06221.1},
  annote =	{Keywords: Lighting Design and Image Relighting, Non-Photorealistic Rendering, Technical Illustration, Medical Illustration, Computational Color Harmony, Color Dynamics , Color Environmental Design, Color Preferences / Effects and Roles of Colors}
}
Document
06221 Dagstuhl Report – Computational Aesthetics in Graphics, Visualization and Imaging

Authors: Bruce Gooch, László Neumann, Werner Purgathofer, and Mateu Sbert

Published in: Dagstuhl Seminar Proceedings, Volume 6221, Computational Aesthetics in Graphics, Visualization and Imaging (2007)


Abstract
The Dagstuhl-Seminar on Computational Aesthetics in Graphics, Visualization and Imaging took place from 28 May until 2 June, 2006, with 54 registered participants and some visiting PhD students from Germany. The high interest in the topics dealt at the seminar resulted in a tight scheduling of presentations and panel discussions.

Cite as

Bruce Gooch, László Neumann, Werner Purgathofer, and Mateu Sbert. 06221 Dagstuhl Report – Computational Aesthetics in Graphics, Visualization and Imaging. In Computational Aesthetics in Graphics, Visualization and Imaging. Dagstuhl Seminar Proceedings, Volume 6221, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{gooch_et_al:DagSemProc.06221.2,
  author =	{Gooch, Bruce and Neumann, L\'{a}szl\'{o} and Purgathofer, Werner and Sbert, Mateu},
  title =	{{06221 Dagstuhl Report – Computational Aesthetics in Graphics, Visualization and Imaging}},
  booktitle =	{Computational Aesthetics in Graphics, Visualization and Imaging},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6221},
  editor =	{Bruce Gooch and L\'{a}szl\'{o} Neumann and Werner Purgathofer and Mateu Sbert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06221.2},
  URN =		{urn:nbn:de:0030-drops-8749},
  doi =		{10.4230/DagSemProc.06221.2},
  annote =	{Keywords: Lighting Design and Image Relighting, Non-Photorealistic Rendering, Technical Illustration, Medical Illustration, Computational Color Harmony, Color D Color Preferences / Effects and Roles of Colors}
}
  • Refine by Author
  • 4 Neumann, Eike
  • 4 Ouaknine, Joël
  • 4 Worrell, James
  • 2 D'Costa, Julian
  • 2 Gooch, Bruce
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Logic and verification
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Spectra of graphs
  • Show More...

  • Refine by Keyword
  • 2 Compact semialgebraic sets
  • 2 Computational Color Harmony
  • 2 Discrete linear dynamical systems
  • 2 Lighting Design and Image Relighting
  • 2 Medical Illustration
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2007
  • 2 2021
  • 2 2022
  • 1 2019
  • 1 2020

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