13 Search Results for "Downey, Rod"

Document
DOI: 10.4230/LIPIcs.ESA.2025.55
Safe Sequences via Dominators in DAGs for Path-Covering Problems

Authors: Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
A path-covering problem on a directed acyclic graph (DAG) requires finding a set of source-to-sink paths that cover all the nodes, all the arcs, or subsets thereof, and additionally they are optimal with respect to some function. In this paper we study safe sequences of nodes or arcs, namely sequences that appear in some path of every path cover of a DAG. We show that safe sequences admit a simple characterization via cutnodes. Moreover, we establish a connection between maximal safe sequences and leaf-to-root paths in the source- and sink-dominator trees of the DAG, which may be of independent interest in the extensive literature on dominators. With dominator trees, safe sequences admit an O(n)-size representation and a linear-time output-sensitive enumeration algorithm running in time O(m + o), where n and m are the number of nodes and arcs, respectively, and o is the total length of the maximal safe sequences. We then apply maximal safe sequences to simplify Integer Linear Programs (ILPs) for two path-covering problems, LeastSquares and MinPathError, which are at the core of RNA transcript assembly problems from bioinformatics. On various datasets, maximal safe sequences can be computed in under 0.1 seconds per graph, on average, and ILP solvers whose search space is reduced in this manner exhibit significant speed-ups. For example on graphs with a large width, average speed-ups are in the range 50-250× for MinPathError and in the range 80-350× for LeastSquares. Optimizing ILPs using safe sequences can thus become a fast building block of practical RNA transcript assembly tools, and more generally, of path-covering problems.
Cite as

Francisco Sena, Romeo Rizzi, and Alexandru I. Tomescu. Safe Sequences via Dominators in DAGs for Path-Covering Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sena_et_al:LIPIcs.ESA.2025.55,
  author =	{Sena, Francisco and Rizzi, Romeo and Tomescu, Alexandru I.},
  title =	{{Safe Sequences via Dominators in DAGs for Path-Covering Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.55},
  URN =		{urn:nbn:de:0030-drops-245230},
  doi =		{10.4230/LIPIcs.ESA.2025.55},
  annote =	{Keywords: directed acyclic graph, path cover, dominator tree, integer linear programming, least squares, minimum path error}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.90
Elimination Distance to Dominated Clusters

Authors: Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
In the Dominated Cluster Deletion problem, we are given an undirected graph G and integers k and d and the question is to decide whether there exists a set of at most k vertices whose removal results in a graph in which each connected component has a dominating set of size at most d. In the Elimination Distance to Dominated Clusters problem, we are again given an undirected graph G and integers k and d and the question is to decide whether we can recursively delete vertices up to depth k such that each remaining connected component has a dominating set of size at most d. Bentert et al. [Bentert et al., MFCS 2024] recently provided an almost complete classification of the parameterized complexity of Dominated Cluster Deletion with respect to the parameters k, d, c, and Δ, where c and Δ are the degeneracy, and the maximum degree of the input graph, respectively. In particular, they provided a non-uniform algorithm with running time f(k,d)⋅ n^{𝒪(d)}. They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter k + d + c. We provide a uniform algorithm running in time f(k,d)⋅ n^{𝒪(d)} for both Dominated Cluster Deletion and Elimination Distance to Dominated Clusters. We furthermore show that both problems are FPT when parameterized by k+d+𝓁, where 𝓁 is the semi-ladder index of the input graph, a parameter that is upper bounded and may be much smaller than the degeneracy c, positively answering the open question of Bentert et al. We further complete the picture by providing an almost full classification for the parameterized complexity and kernelization complexity of Elimination Distance to Dominated Clusters. The one difficult base case that remains open is whether Treedepth (the case d = 0) is NP-hard on graphs of bounded maximum degree.
Cite as

Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. Elimination Distance to Dominated Clusters. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schirrmacher_et_al:LIPIcs.MFCS.2025.90,
  author =	{Schirrmacher, Nicole and Siebertz, Sebastian and Vigny, Alexandre},
  title =	{{Elimination Distance to Dominated Clusters}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.90},
  URN =		{urn:nbn:de:0030-drops-241978},
  doi =		{10.4230/LIPIcs.MFCS.2025.90},
  annote =	{Keywords: Graph theory, Fixed-parameter algorithms, Dominated cluster, Elimination distance}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.90
Revisiting Directed Disjoint Paths on Tournaments (And Relatives)

Authors: Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c ≤ k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.
Cite as

Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau. Revisiting Directed Disjoint Paths on Tournaments (And Relatives). In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dec.m.gomes_et_al:LIPIcs.ICALP.2025.90,
  author =	{de C. M. Gomes, Guilherme and Lopes, Raul and Sau, Ignasi},
  title =	{{Revisiting Directed Disjoint Paths on Tournaments (And Relatives)}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.90},
  URN =		{urn:nbn:de:0030-drops-234678},
  doi =		{10.4230/LIPIcs.ICALP.2025.90},
  annote =	{Keywords: directed graphs, tournaments, semicomplete digraphs, directed disjoint paths, congestion, parameterized complexity, directed pathwidth}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.142
Online and Feasible Presentability: From Trees to Modal Algebras

Authors: Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures.
Cite as

Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski. Online and Feasible Presentability: From Trees to Modal Algebras. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 142:1-142:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bazhenov_et_al:LIPIcs.ICALP.2025.142,
  author =	{Bazhenov, Nikolay and Kaloci\'{n}ski, Dariusz and Wroc{\l}awski, Micha{\l}},
  title =	{{Online and Feasible Presentability: From Trees to Modal Algebras}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{142:1--142:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.142},
  URN =		{urn:nbn:de:0030-drops-235190},
  doi =		{10.4230/LIPIcs.ICALP.2025.142},
  annote =	{Keywords: Algebraic structure, computable structure, fully primitive recursive structure, punctual structure, polynomial-time computable structure, punctual robustness, tree, semilattice, lattice, Boolean algebra, modal algebra}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1810
Kolmogorov Complexity and Solovay Functions

Authors: Laurent Bienvenu and Rod Downey

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

Abstract
Solovay (1975) proved that there exists a computable upper bound~$f$ of the prefix-free Kolmogorov complexity function~$K$ such that $f(x)=K(x)$ for infinitely many~$x$. In this paper, we consider the class of computable functions~$f$ such that $K(x) \leq f(x)+O(1)$ for all~$x$ and $f(x) \leq K(x)+O(1)$ for infinitely many~$x$, which we call Solovay functions. We show that Solovay functions present interesting connections with randomness notions such as Martin-L\"of randomness and K-triviality.
Cite as

Laurent Bienvenu and Rod Downey. Kolmogorov Complexity and Solovay Functions. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 147-158, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bienvenu_et_al:LIPIcs.STACS.2009.1810,
  author =	{Bienvenu, Laurent and Downey, Rod},
  title =	{{Kolmogorov Complexity and Solovay Functions}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{147--158},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1810},
  URN =		{urn:nbn:de:0030-drops-18107},
  doi =		{10.4230/LIPIcs.STACS.2009.1810},
  annote =	{Keywords: Algorithmic randomness, Kolmogorov complexity, K-triviality}
}
Document
DOI: 10.4230/DagSemProc.07441.1
07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures

Authors: Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
From 28.10. to 02.11.2007, the Dagstuhl Seminar 07441 ``Algorithmic-Logical Theory of Infinite Structures'' 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

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.1,
  author =	{Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.},
  title =	{{07441 Abstracts Collection – Algorithmic-Logical Theory of Infinite Structures}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.1},
  URN =		{urn:nbn:de:0030-drops-14122},
  doi =		{10.4230/DagSemProc.07441.1},
  annote =	{Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems}
}
Document
DOI: 10.4230/DagSemProc.07441.2
07441 Summary – Algorithmic-Logical Theory of Infinite Structures

Authors: Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
One of the important research fields of theoretical and applied computer science and mathematics is the study of algorithmic, logical and model theoretic properties of structures and their interactions. By a structure we mean typical objects that arise in computer science and mathematics such as data structures, programs, transition systems, graphs, large databases, XML documents, algebraic systems including groups, integers, fields, Boolean algebras and so on.
Cite as

Rod Downey, Bakhadyr Khoussainov, Dietrich Kuske, Markus Lohrey, and Moshe Y. Vardi. 07441 Summary – Algorithmic-Logical Theory of Infinite Structures. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.07441.2,
  author =	{Downey, Rod and Khoussainov, Bakhadyr and Kuske, Dietrich and Lohrey, Markus and Vardi, Moshe Y.},
  title =	{{07441 Summary – Algorithmic-Logical Theory of Infinite Structures}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.2},
  URN =		{urn:nbn:de:0030-drops-14111},
  doi =		{10.4230/DagSemProc.07441.2},
  annote =	{Keywords: Theories of infinite structures , computable model theory and automatic structures , model checking infinite systems}
}
Document
DOI: 10.4230/DagSemProc.07441.3
Application of verification techniques to inverse monoids

Authors: Markus Lohrey

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
The word problem for inverse monoids generated by a set $Gamma$ subject to relations of the form $e=f$, where $e$ and $f$ are both idempotents in the free inverse monoid generated by $Gamma$, is investigated. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node $x$ to a node $y$ that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, some results on free partially commutative inverse monoids are presented.
Cite as

Markus Lohrey. Application of verification techniques to inverse monoids. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lohrey:DagSemProc.07441.3,
  author =	{Lohrey, Markus},
  title =	{{Application of verification techniques to inverse monoids}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.3},
  URN =		{urn:nbn:de:0030-drops-14109},
  doi =		{10.4230/DagSemProc.07441.3},
  annote =	{Keywords: Inverse monoids, word problems, Cayley-graphs, complexity}
}
Document
DOI: 10.4230/DagSemProc.07441.4
Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic

Authors: Dietrich Kuske

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
We investigate the relation between the theory of the iterations in the sense of Shelah-Stupp and of Muchnik, resp., and the theory of the base structure for several logics. These logics are obtained from the restriction of set quantification in monadic second order logic to certain subsets like, e.g., finite sets, chains, and finite unions of chains. We show that these theories of the Shelah-Stupp iteration can be reduced to corresponding theories of the base structure. This fails for Muchnik's iteration.
Cite as

Dietrich Kuske. Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kuske:DagSemProc.07441.4,
  author =	{Kuske, Dietrich},
  title =	{{Compatibility of Shelah and Stupp's and of Muchnik's iteration with fragments of monadic second order logic}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.4},
  URN =		{urn:nbn:de:0030-drops-14078},
  doi =		{10.4230/DagSemProc.07441.4},
  annote =	{Keywords: Logic in computer science, Rabin's tree theorem}
}
Document
DOI: 10.4230/DagSemProc.07441.5
PDL with Intersection and Converse is 2EXP-complete

Authors: Stefan Göller, Markus Lohrey, and Carsten Lutz

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
The logic ICPDL is the expressive extension of Propositional Dynamic Logic (PDL), which admits intersection and converse as program operators. The result of this paper is containment of ICPDL-satisfiability in $2$EXP, which improves the previously known non-elementary upper bound and implies $2$EXP-completeness due to an existing lower bound for PDL with intersection (IPDL). The proof proceeds showing that every satisfiable ICPDL formula has model of tree width at most two. Next, we reduce satisfiability in ICPDL to $omega$-regular tree satisfiability in ICPDL. In the latter problem the set of possible models is restricted to trees of an $omega$-regular tree language. In the final step,$omega$-regular tree satisfiability is reduced the emptiness problem for alternating two-way automata on infinite trees. In this way, a more elegant proof is obtained for Danecki's difficult result that satisfiability in IPDL is in $2EXP$.
Cite as

Stefan Göller, Markus Lohrey, and Carsten Lutz. PDL with Intersection and Converse is 2EXP-complete. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{goller_et_al:DagSemProc.07441.5,
  author =	{G\"{o}ller, Stefan and Lohrey, Markus and Lutz, Carsten},
  title =	{{PDL with Intersection and Converse is 2EXP-complete}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.5},
  URN =		{urn:nbn:de:0030-drops-14093},
  doi =		{10.4230/DagSemProc.07441.5},
  annote =	{Keywords: Satisfiability, Propositional Dynamic Logic, Computational Complexity}
}
Document
DOI: 10.4230/DagSemProc.07441.6
Tree Automata Make Ordinal Theory Easy

Authors: Thierry Cachat

Published in: Dagstuhl Seminar Proceedings, Volume 7441, Algorithmic-Logical Theory of Infinite Structures (2008)

Abstract
We give a new simple proof of the decidability of the First Order Theory of $(w^{w^i},+)$ and the Monadic Second Order Theory of $(w^i,<)$, improving the complexity in both cases. Our algorithm is based on tree automata and a new representation of (sets of) ordinals by (infinite) trees.
Cite as

Thierry Cachat. Tree Automata Make Ordinal Theory Easy. In Algorithmic-Logical Theory of Infinite Structures. Dagstuhl Seminar Proceedings, Volume 7441, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{cachat:DagSemProc.07441.6,
  author =	{Cachat, Thierry},
  title =	{{Tree Automata Make Ordinal Theory Easy}},
  booktitle =	{Algorithmic-Logical Theory of Infinite Structures},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7441},
  editor =	{Rod Downey and Bakhadyr Khoussainov and Dietrich Kuske and Markus Lohrey and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07441.6},
  URN =		{urn:nbn:de:0030-drops-14082},
  doi =		{10.4230/DagSemProc.07441.6},
  annote =	{Keywords: Ordinals, First Order theory, Monadic Second Order Theory, tree automata}
}
Document
DOI: 10.4230/DagSemProc.05301.1
05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
From 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. This is a collection of abstracts of the presentations given during the seminar.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.1,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Abstracts Collection – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.1},
  URN =		{urn:nbn:de:0030-drops-4405},
  doi =		{10.4230/DagSemProc.05301.1},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}
Document
DOI: 10.4230/DagSemProc.05301.2
05301 Summary – Exact Algorithms and Fixed-Parameter Tractability

Authors: Rod Downey, Martin Grohe, and Gerhard Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 5301, Exact Algorithms and Fixed-Parameter Tractability (2006)

Abstract
Summary of the Dagstuhl Seminar held 24. July - 29. July 2005.
Cite as

Rod Downey, Martin Grohe, and Gerhard Woeginger. 05301 Summary – Exact Algorithms and Fixed-Parameter Tractability. In Exact Algorithms and Fixed-Parameter Tractability. Dagstuhl Seminar Proceedings, Volume 5301, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{downey_et_al:DagSemProc.05301.2,
  author =	{Downey, Rod and Grohe, Martin and Woeginger, Gerhard},
  title =	{{05301 Summary – Exact Algorithms and Fixed-Parameter Tractability}},
  booktitle =	{Exact Algorithms and Fixed-Parameter Tractability},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5301},
  editor =	{Rod Downey and Martin Grohe and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05301.2},
  URN =		{urn:nbn:de:0030-drops-4396},
  doi =		{10.4230/DagSemProc.05301.2},
  annote =	{Keywords: Fixed-parameter tractability, parameterized complexity, exact algorithms}
}
  • Refine by Type
  • 13 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2009
  • 6 2008
  • 2 2006

  • Refine by Author
  • 5 Downey, Rod
  • 4 Lohrey, Markus
  • 3 Kuske, Dietrich
  • 2 Grohe, Martin
  • 2 Khoussainov, Bakhadyr
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 8 DagSemProc

  • Refine by Classification
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Applied computing → Sequencing and genotyping technologies
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Computability
  • Show More...

  • Refine by Keyword
  • 3 parameterized complexity
  • 2 Fixed-parameter tractability
  • 2 Theories of infinite structures
  • 2 computable model theory and automatic structures
  • 2 exact algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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