3 Search Results for "Wrona, Michał"

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2021.138
Smooth Approximations and Relational Width Collapses

Authors: Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona

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

Abstract
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well.
Cite as

Antoine Mottet, Tomáš Nagy, Michael Pinsker, and Michał Wrona. Smooth Approximations and Relational Width Collapses. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mottet_et_al:LIPIcs.ICALP.2021.138,
  author =	{Mottet, Antoine and Nagy, Tom\'{a}\v{s} and Pinsker, Michael and Wrona, Micha{\l}},
  title =	{{Smooth Approximations and Relational Width Collapses}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{138:1--138: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.138},
  URN =		{urn:nbn:de:0030-drops-142075},
  doi =		{10.4230/LIPIcs.ICALP.2021.138},
  annote =	{Keywords: local consistency, bounded width, constraint satisfaction problems, polymorphisms, smooth approximations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.39
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

Authors: Michał Wrona

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures first-order definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of local-consistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP(?) for first-order expansions ? of countably infinite homogeneous graphs ℋ := (A; E), which happen all to be finitely bounded. We study our problem for structures ? that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of CSP(?) not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. Our main result is that the structures ? under consideration have relational width exactly (2, ?_ℋ) where ?_ℋ is the maximal size of a forbidden subgraph of ℋ, but not smaller than 3. It beats the upper bound: (2 m, 3 m) where m = max(arity(?)+1, ?, 3) and arity(?) is the largest arity of a relation in ?, which follows from a sufficient condition implying bounded relational width given in [Manuel Bodirsky and Antoine Mottet, 2018]. Since ?_ℋ may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures ?, whose relational width, if finite, is always at most (2,3).
Cite as

Michał Wrona. Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 39:1-39:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wrona:LIPIcs.STACS.2020.39,
  author =	{Wrona, Micha{\l}},
  title =	{{Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{39:1--39:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.39},
  URN =		{urn:nbn:de:0030-drops-119000},
  doi =		{10.4230/LIPIcs.STACS.2020.39},
  annote =	{Keywords: Constraint Satisfaction, Homogeneous Graphs, Bounded Width, Strict Width, Relational Width, Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.CSL.2013.615
The Complexity of Abduction for Equality Constraint Languages

Authors: Johannes Schmidt and Michał Wrona

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
Abduction is a form of nonmonotonic reasoning that looks for an explanation for an observed manifestation according to some knowledge base. One form of the abduction problem studied in the literature is the propositional abduction problem parameterized by a structure \Gamma over the two-element domain. In that case, the knowledge base is a set of constraints over \Gamma, the manifestation and explanation are propositional formulas. In this paper, we follow a similar route. Yet, we consider abduction over infinite domain. We study the equality abduction problem parameterized by a relational first-order structure \Gamma over the natural numbers such that every relation in \Gamma is definable by a Boolean combination of equalities, a manifestation is a literal of the form (x = y) or (x != y), and an explanation is a set of such literals. Our main contribution is a complete complexity characterization of the equality abduction problem. We prove that depending on \Gamma, it is \Sigma^P_2-complete, or NP-complete, or in P.
Cite as

Johannes Schmidt and Michał Wrona. The Complexity of Abduction for Equality Constraint Languages. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 615-633, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:LIPIcs.CSL.2013.615,
  author =	{Schmidt, Johannes and Wrona, Micha{\l}},
  title =	{{The Complexity of Abduction for Equality Constraint Languages}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{615--633},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.615},
  URN =		{urn:nbn:de:0030-drops-42229},
  doi =		{10.4230/LIPIcs.CSL.2013.615},
  annote =	{Keywords: Abduction, infinite structures, equality constraint languages, computational complexity, algebraic approach}
}
  • Refine by Author
  • 3 Wrona, Michał
  • 1 Mottet, Antoine
  • 1 Nagy, Tomáš
  • 1 Pinsker, Michael
  • 1 Schmidt, Johannes

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Logic
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Abduction
  • 1 Bounded Width
  • 1 Computational Complexity
  • 1 Constraint Satisfaction
  • 1 Homogeneous Graphs
  • Show More...

  • Refine by Type
  • 3 document

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