4 Search Results for "Clause, Michael"

Document
DOI: 10.4230/LIPIcs.TIME.2021.10
Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic

Authors: Vladislav Ryzhikov, Yury Savateev, and Michael Zakharyaschev

Published in: LIPIcs, Volume 206, 28th International Symposium on Temporal Representation and Reasoning (TIME 2021)

Abstract
Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (ℤ, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC⁰, ACC⁰ and NC¹ coincides with FO(<,≡)-rewritability using unary predicates x ≡ 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We then show that deciding FO(<)-, FO(<,≡)- and FO(<,MOD)-rewritability of LTL OMQs is ExpSpace-complete, and that these problems become PSpace-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,≡)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSpace-, Π₂^p- and coNP-complete.
Cite as

Vladislav Ryzhikov, Yury Savateev, and Michael Zakharyaschev. Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic. In 28th International Symposium on Temporal Representation and Reasoning (TIME 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 206, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ryzhikov_et_al:LIPIcs.TIME.2021.10,
  author =	{Ryzhikov, Vladislav and Savateev, Yury and Zakharyaschev, Michael},
  title =	{{Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic}},
  booktitle =	{28th International Symposium on Temporal Representation and Reasoning (TIME 2021)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-206-8},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{206},
  editor =	{Combi, Carlo and Eder, Johann and Reynolds, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2021.10},
  URN =		{urn:nbn:de:0030-drops-147867},
  doi =		{10.4230/LIPIcs.TIME.2021.10},
  annote =	{Keywords: Linear temporal logic, ontology-mediated query, first-order rewritability}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.17
Branching Programs with Bounded Repetitions and Flow Formulas

Authors: Anastasia Sofronova and Dmitry Sokolov

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. [László Lovász et al., 1995] who showed the equivalence between regular Resolution and read-once branching programs for "unsatisfied clause search problem" (Search_φ). This connection is widely used, in particular, in the recent breakthrough result about the Clique problem in regular Resolution by Atserias et al. [Albert Atserias et al., 2018]. We study the branching programs with bounded repetitions, so-called (1,+k)-BPs (Sieling [Detlef Sieling, 1996]) in application to the Search_φ problem. On the one hand, it is a natural generalization of read-once branching programs. On the other hand, this model gives a powerful proof system that can efficiently certify the unsatisfiability of a wide class of formulas that is hard for Resolution (Knop [Alexander Knop, 2017]). We deal with Search_φ that is "relatively easy" compared to all known hard examples for the (1,+k)-BPs. We introduce the first technique for proving exponential lower bounds for the (1,+k)-BPs on Search_φ. To do it we combine a well-known technique for proving lower bounds on the size of branching programs [Detlef Sieling, 1996; Detlef Sieling and Ingo Wegener, 1994; Stasys Jukna and Alexander A. Razborov, 1998] with the modification of the "closure" technique [Michael Alekhnovich et al., 2004; Michael Alekhnovich and Alexander A. Razborov, 2003]. In contrast with most Resolution lower bounds, our technique uses not only "local" properties of the formula, but also a "global" structure. Our hard examples are based on the Flow formulas introduced in [Michael Alekhnovich and Alexander A. Razborov, 2003].
Cite as

Anastasia Sofronova and Dmitry Sokolov. Branching Programs with Bounded Repetitions and Flow Formulas. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sofronova_et_al:LIPIcs.CCC.2021.17,
  author =	{Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{Branching Programs with Bounded Repetitions and Flow Formulas}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.17},
  URN =		{urn:nbn:de:0030-drops-142915},
  doi =		{10.4230/LIPIcs.CCC.2021.17},
  annote =	{Keywords: proof complexity, branching programs, bounded repetitions, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.62
Static Type Checking for the Q Functional Language in Prolog

Authors: Zsolt Zombori, János Csorba, and Péter Szeredi

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
We describe an application of Prolog: a type checking tool for the Q functional language. Q is a terse vector processing language, a descendant of APL, which is getting more and more popular, especially in financial applications. Q is a dynamically typed language, much like Prolog. Extending Q with static typing improves both the readability of programs and programmer productivity, as type errors are discovered by the tool at compile time, rather than through debugging the program execution. We designed a type description syntax for Q and implemented a parser for both the Q language and its type extension. We then implemented a type checking algorithm using constraints. As most built-in function names of Q are overloaded, i.e. their meaning depends on the argument types, a quite complex system of constraints had to be implemented. Prolog proved to be an ideal implementation language for the task at hand. We used Definite Clause Grammars for parsing and Constraint Handling Rules for the type checking algorithm. In the paper we describe the main problems solved and the experiences gained in the development of the type checking tool.
Cite as

Zsolt Zombori, János Csorba, and Péter Szeredi. Static Type Checking for the Q Functional Language in Prolog. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 62-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{zombori_et_al:LIPIcs.ICLP.2011.62,
  author =	{Zombori, Zsolt and Csorba, J\'{a}nos and Szeredi, P\'{e}ter},
  title =	{{Static Type Checking for the Q Functional Language in Prolog}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{62--72},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.62},
  URN =		{urn:nbn:de:0030-drops-31718},
  doi =		{10.4230/LIPIcs.ICLP.2011.62},
  annote =	{Keywords: logic programming, types, static type checking, constraints, CHR, DCG}
}
Document
DOI: 10.4230/DagSemRep.371
Multimedia Retrieval (Dagstuhl Seminar 03112)

Authors: Michael Clause, Rolf Klein, and Ian H. Witten

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

Abstract
Cite as

Michael Clause, Rolf Klein, and Ian H. Witten. Multimedia Retrieval (Dagstuhl Seminar 03112). Dagstuhl Seminar Report 371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{clause_et_al:DagSemRep.371,
  author =	{Clause, Michael and Klein, Rolf and Witten, Ian H.},
  title =	{{Multimedia Retrieval (Dagstuhl Seminar 03112)}},
  pages =	{1--4},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{371},
  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.371},
  URN =		{urn:nbn:de:0030-drops-152517},
  doi =		{10.4230/DagSemRep.371},
}
  • Refine by Author
  • 1 Clause, Michael
  • 1 Csorba, János
  • 1 Klein, Rolf
  • 1 Ryzhikov, Vladislav
  • 1 Savateev, Yury
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Modal and temporal logics
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 CHR
  • 1 DCG
  • 1 Linear temporal logic
  • 1 bounded repetitions
  • 1 branching programs
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2003
  • 1 2011

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