4 Search Results for "Th�ne, Sebastian"


Document
Structural Properties of the First-Order Transduction Quasiorder

Authors: Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)


Abstract
Logical transductions provide a very useful tool to encode classes of structures inside other classes of structures. In this paper we study first-order (FO) transductions and the quasiorder they induce on infinite classes of finite graphs. Surprisingly, this quasiorder is very complex, though shaped by the locality properties of first-order logic. This contrasts with the conjectured simplicity of the monadic second order (MSO) transduction quasiorder. We first establish a local normal form for FO transductions, which is of independent interest. Then we prove that the quotient partial order is a bounded distributive join-semilattice, and that the subposet of additive classes is also a bounded distributive join-semilattice. The FO transduction quasiorder has a great expressive power, and many well studied class properties can be defined using it. We apply these structural properties to prove, among other results, that FO transductions of the class of paths are exactly perturbations of classes with bounded bandwidth, that the local variants of monadic stability and monadic dependence are equivalent to their (standard) non-local versions, and that the classes with pathwidth at most k, for k ≥ 1 form a strict hierarchy in the FO transduction quasiorder.

Cite as

Jaroslav Nešetřil, Patrice Ossona de Mendez, and Sebastian Siebertz. Structural Properties of the First-Order Transduction Quasiorder. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{nesetril_et_al:LIPIcs.CSL.2022.31,
  author =	{Ne\v{s}et\v{r}il, Jaroslav and Ossona de Mendez, Patrice and Siebertz, Sebastian},
  title =	{{Structural Properties of the First-Order Transduction Quasiorder}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.31},
  URN =		{urn:nbn:de:0030-drops-157514},
  doi =		{10.4230/LIPIcs.CSL.2022.31},
  annote =	{Keywords: Finite model theory, first-order transductions, structural graph theory}
}
Document
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

Authors: Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)


Abstract
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these, called Isomorphism With Restrictions, is to decide for two given graphs X_1=(V,E_1) and X_2=(V,E_2) and a subset R\subseteq V\times V of forbidden pairs whether there is an isomorphism \pi from X_1 to X_2 such that i^\pi\ne j for all (i,j)\in R. We prove that this problem and several of its generalizations are in fact in \FPT: - The problem of deciding whether there is an isomorphism between two graphs that moves k vertices and satisfies Lubiw-style constraints is in FPT, with k and the size of R as parameters. The problem remains in FPT even if a conjunction of disjunctions of such constraints is allowed. As a consequence of the main result it follows that the problem to decide whether there is an isomorphism that moves exactly k vertices is in FPT. This solves a question left open in our article on exact weight automorphisms [STACS 2017]. - When the number of moved vertices is unrestricted, finding isomorphisms that satisfy a CNF of Lubiw-style constraints can be solved in FPT with access to a GI oracle. - Checking if there is an isomorphism π between two graphs with complexity t is also in FPT with t as parameter, where the complexity of a permutation is the Cayley measure defined as the minimum number t such that \pi can be expressed as a product of t transpositions. - We consider a more general problem in which the vertex set of a graph X is partitioned into Red and Blue, and we are interested in an automorphism that stabilizes Red and Blue and moves exactly k vertices in Blue, where k is the parameter. This problem was introduced by [Downey and Fellows 1999], and we showed [STACS 2017] that it is W[1]-hard even with color classes of size 4 inside Red. Now, for color classes of size at most 3 inside Red, we show the problem is in FPT. In the non-parameterized setting, all these problems are NP-complete. Also, they all generalize in several ways the problem to decide whether there is an isomorphism between two graphs that moves at most k vertices, shown to be in FPT by Schweitzer [ESA 2011].

Cite as

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán. Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.IPEC.2017.2,
  author =	{Arvind, Vikraman and K\"{o}bler, Johannes and Kuhnert, Sebastian and Tor\'{a}n, Jacobo},
  title =	{{Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.2},
  URN =		{urn:nbn:de:0030-drops-85690},
  doi =		{10.4230/LIPIcs.IPEC.2017.2},
  annote =	{Keywords: parameterized algorithms, hypergraph isomorphism, mislabeled graphs}
}
Document
Proof Complexity of Propositional Default Logic

Authors: Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, and Heribert Vollmer

Published in: Dagstuhl Seminar Proceedings, Volume 10061, Circuits, Logic, and Games (2010)


Abstract
Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen's system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti's enhanced calculus for skeptical default reasoning.

Cite as

Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas, and Heribert Vollmer. Proof Complexity of Propositional Default Logic. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 10061, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{beyersdorff_et_al:DagSemProc.10061.5,
  author =	{Beyersdorff, Olaf and Meier, Arne and M\"{u}ller, Sebastian and Thomas, Michael and Vollmer, Heribert},
  title =	{{Proof Complexity of Propositional Default Logic}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10061},
  editor =	{Benjamin Rossman and Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10061.5},
  URN =		{urn:nbn:de:0030-drops-25261},
  doi =		{10.4230/DagSemProc.10061.5},
  annote =	{Keywords: Proof complexity, default logic, sequent calculus}
}
Document
Graph Transformation Based Models of Dynamic Software Architectures and Architectural Styles

Authors: Sebastian Thöne

Published in: Dagstuhl Seminar Proceedings, Volume 4101, Language Engineering for Model-Driven Software Development (2005)


Abstract
no abstract

Cite as

Sebastian Thöne. Graph Transformation Based Models of Dynamic Software Architectures and Architectural Styles. In Language Engineering for Model-Driven Software Development. Dagstuhl Seminar Proceedings, Volume 4101, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{thone:DagSemProc.04101.9,
  author =	{Th\"{o}ne, Sebastian},
  title =	{{Graph Transformation Based Models of Dynamic Software Architectures and Architectural Styles}},
  booktitle =	{Language Engineering for Model-Driven Software Development},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4101},
  editor =	{Jean Bezivin and Reiko Heckel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04101.9},
  URN =		{urn:nbn:de:0030-drops-174},
  doi =		{10.4230/DagSemProc.04101.9},
  annote =	{Keywords: no keywords}
}
  • Refine by Author
  • 1 Arvind, Vikraman
  • 1 Beyersdorff, Olaf
  • 1 Kuhnert, Sebastian
  • 1 Köbler, Johannes
  • 1 Meier, Arne
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Finite Model Theory

  • Refine by Keyword
  • 1 Finite model theory
  • 1 Proof complexity
  • 1 default logic
  • 1 first-order transductions
  • 1 hypergraph isomorphism
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2005
  • 1 2010
  • 1 2018
  • 1 2022

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