5 Search Results for "Batory, Don"

Document
DOI: 10.4230/LIPIcs.ICDT.2025.31
On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators

Authors: Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, and Michael Zakharyaschev

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
Our concern is the data complexity of answering linear monadic datalog queries whose atoms in the rule bodies can be prefixed by operators of linear temporal logic LTL. We first observe that, for data complexity, answering any connected query with operators ○/○- (at the next/previous moment) is either in AC⁰, or in ACC⁰\AC⁰, or NC¹-complete, or L-hard and in NL. Then we show that the problem of deciding L-hardness of answering such queries is PSpace-complete, while checking membership in the classes AC⁰ and ACC⁰ as well as NC¹-completeness can be done in ExpSpace. Finally, we prove that membership in AC⁰ or in ACC⁰, NC¹-completeness, and L-hardness are undecidable for queries with operators ◇/◇- (sometime in the future/past) provided that NC¹ ≠ NL and L ≠ NL.
Cite as

Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, and Michael Zakharyaschev. On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{artale_et_al:LIPIcs.ICDT.2025.31,
  author =	{Artale, Alessandro and Gnatenko, Anton and Ryzhikov, Vladislav and Zakharyaschev, Michael},
  title =	{{On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.31},
  URN =		{urn:nbn:de:0030-drops-229723},
  doi =		{10.4230/LIPIcs.ICDT.2025.31},
  annote =	{Keywords: Linear monadic datalog, linear temporal logic, data complexity}
}
Document
DOI: 10.4230/LITES.8.2.4
A Hybrid Programming Language for Formal Modeling and Verification of Hybrid Systems

Authors: Eduard Kamburjan, Stefan Mitsch, and Reiner Hähnle

Published in: LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2

Abstract
Designing and modeling complex cyber-physical systems (CPS) faces the double challenge of combined discrete-continuous dynamics and concurrent behavior. Existing formal modeling and verification languages for CPS expose the underlying proof search technology. They lack high-level structuring elements and are not efficiently executable. The ensuing modeling gap renders formal CPS models hard to understand and to validate. We propose a high-level programming-based approach to formal modeling and verification of hybrid systems as a hybrid extension of an Active Objects language. Well-structured hybrid active programs and requirements allow automatic, reachability-preserving translation into differential dynamic logic, a logic for hybrid (discrete-continuous) programs. Verification is achieved by discharging the resulting formulas with the theorem prover KeYmaera X. We demonstrate the usability of our approach with case studies.
Cite as

Eduard Kamburjan, Stefan Mitsch, and Reiner Hähnle. A Hybrid Programming Language for Formal Modeling and Verification of Hybrid Systems. In LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2, pp. 04:1-04:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{kamburjan_et_al:LITES.8.2.4,
  author =	{Kamburjan, Eduard and Mitsch, Stefan and H\"{a}hnle, Reiner},
  title =	{{A Hybrid Programming Language for Formal Modeling and Verification of Hybrid Systems}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{04:1--04:34},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.2.4},
  URN =		{urn:nbn:de:0030-drops-192965},
  doi =		{10.4230/LITES.8.2.4},
  annote =	{Keywords: Active Objects, Differential Dynamic Logic, Hybrid Systems}
}
Document
DOI: 10.4230/DagSemProc.08281.1
08281 Abstracts Collection – Software Engineering for Trailor-made Data Management

Authors: Sven Apel, Don Batory, Goetz Graefe, Gunter Saake, and Olaf Spinczyk

Published in: Dagstuhl Seminar Proceedings, Volume 8281, Software Engineering for Tailor-made Data Management (2008)

Abstract
From July 6th to July 11th, 2008, the Dagstuhl Seminar 08281 ``Software Engineering for Tailor-made Data Management'' 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

Sven Apel, Don Batory, Goetz Graefe, Gunter Saake, and Olaf Spinczyk. 08281 Abstracts Collection – Software Engineering for Trailor-made Data Management. In Software Engineering for Tailor-made Data Management. Dagstuhl Seminar Proceedings, Volume 8281, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{apel_et_al:DagSemProc.08281.1,
  author =	{Apel, Sven and Batory, Don and Graefe, Goetz and Saake, Gunter and Spinczyk, Olaf},
  title =	{{08281  Abstracts Collection – Software Engineering for Trailor-made Data Management}},
  booktitle =	{Software Engineering for Tailor-made Data Management},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8281},
  editor =	{Sven Apel and Don Batory and Goetz Graefe and Gunter Saake and Olaf Spynczyk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08281.1},
  URN =		{urn:nbn:de:0030-drops-15796},
  doi =		{10.4230/DagSemProc.08281.1},
  annote =	{Keywords: Software Engineering, Data Management, Software Product Lines, Embedded Systems}
}
Document
DOI: 10.4230/DagSemProc.08281.2
08281 Executive Summary – Software Engineering for Tailor-made Data Management

Authors: Sven Apel, Don Batory, Goetz Graefe, Gunter Saake, and Olaf Spinczyk

Published in: Dagstuhl Seminar Proceedings, Volume 8281, Software Engineering for Tailor-made Data Management (2008)

Abstract
Tailor-made data management software (DMS) is not only important in the field of embedded systems. DMS that incorporates only features that are required bear the potential to strip down the code base and to improve reliability and maintainability. In the past 20 years several new technologies have emerged that aim at lean, efficient, and well-structured software, which should also be applicable to DMS. In the Dagstuhl Seminar ``Software Engineering for Tailor-made Data Management'', July 6h to July 11th, 2008, 29 researchers from 7 countries discussed the development, application, and assessment of these new technologies in the context of DMS.
Cite as

Sven Apel, Don Batory, Goetz Graefe, Gunter Saake, and Olaf Spinczyk. 08281 Executive Summary – Software Engineering for Tailor-made Data Management. In Software Engineering for Tailor-made Data Management. Dagstuhl Seminar Proceedings, Volume 8281, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{apel_et_al:DagSemProc.08281.2,
  author =	{Apel, Sven and Batory, Don and Graefe, Goetz and Saake, Gunter and Spinczyk, Olaf},
  title =	{{08281 Executive Summary – Software Engineering for Tailor-made Data Management}},
  booktitle =	{Software Engineering for Tailor-made Data Management},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8281},
  editor =	{Sven Apel and Don Batory and Goetz Graefe and Gunter Saake and Olaf Spynczyk},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08281.2},
  URN =		{urn:nbn:de:0030-drops-15780},
  doi =		{10.4230/DagSemProc.08281.2},
  annote =	{Keywords: Software Engineering, Data Management, Tailoring, Embedded Systems}
}
Document
DOI: 10.4230/DagSemRep.373
Domain-Specific Program Generation (Dagstuhl Seminar 03131)

Authors: Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky

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

Abstract
Cite as

Don Batory, Charles Consel, Christian Lengauer, and Martin Odersky. Domain-Specific Program Generation (Dagstuhl Seminar 03131). Dagstuhl Seminar Report 373, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{batory_et_al:DagSemRep.373,
  author =	{Batory, Don and Consel, Charles and Lengauer, Christian and Odersky, Martin},
  title =	{{Domain-Specific Program Generation (Dagstuhl Seminar 03131)}},
  pages =	{1--8},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{373},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.373},
  URN =		{urn:nbn:de:0030-drops-152531},
  doi =		{10.4230/DagSemRep.373},
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 2 2008
  • 1 2003

  • Refine by Author
  • 3 Batory, Don
  • 2 Apel, Sven
  • 2 Graefe, Goetz
  • 2 Saake, Gunter
  • 2 Spinczyk, Olaf
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 LITES
  • 1 DagSemRep
  • 2 DagSemProc

  • Refine by Classification
  • 1 Computing methodologies → Distributed programming languages
  • 1 Computing methodologies → Model verification and validation
  • 1 Theory of computation → Database query processing and optimization (theory)
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Timed and hybrid models

  • Refine by Keyword
  • 2 Data Management
  • 2 Embedded Systems
  • 2 Software Engineering
  • 1 Active Objects
  • 1 Differential Dynamic Logic
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact