Uniform Guarded Fragments

Reijo Jaakkola

doi:10.1007/978-3-030-99253-8_21

Uniform Guarded Fragments

Reijo Jaakkola

Computing Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

12 Downloads (Pure)

Abstract

In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.

Original language	English
Title of host publication	Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings
Editors	Patricia Bouyer, Lutz Schröder
Publisher	Springer
Pages	409-427
Number of pages	19
ISBN (Print)	9783030992521
DOIs	https://doi.org/10.1007/978-3-030-99253-8_21
Publication status	Published - 2022
Publication type	A4 Article in conference proceedings
Event	European Joint Conferences on Theory and Practice of Software - Munich, Germany Duration: 4 Apr 2022 → 6 Apr 2022

Publication series

Name	Lecture Notes in Computer Science
Volume	13242 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Joint Conferences on Theory and Practice of Software
Country/Territory	Germany
City	Munich
Period	4/04/22 → 6/04/22

Keywords

Guarded fragment
Interpolation
Satisfiability problem

Publication forum classification

Publication forum level 1

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-99253-8_21Licence: CC BY

Uniform Guarded FragmentsFinal published version, 706 KBLicence: CC BY

https://urn.fi/URN:NBN:fi:tuni-202205104610Licence: CC BY

Cite this

Jaakkola, R. (2022). Uniform Guarded Fragments. In P. Bouyer, & L. Schröder (Eds.), Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings (pp. 409-427). (Lecture Notes in Computer Science ; Vol. 13242 LNCS). Springer. https://doi.org/10.1007/978-3-030-99253-8_21

@inproceedings{ab2e822b0a0b4c8393dc94f458ce900c,

title = "Uniform Guarded Fragments",

abstract = "In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.",

keywords = "Guarded fragment, Interpolation, Satisfiability problem",

author = "Reijo Jaakkola",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s). jufoid=62555; European Joint Conferences on Theory and Practice of Software ; Conference date: 04-04-2022 Through 06-04-2022",

year = "2022",

doi = "10.1007/978-3-030-99253-8\_21",

language = "English",

isbn = "9783030992521",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "409--427",

editor = "Patricia Bouyer and Lutz Schr{\"o}der",

booktitle = "Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings",

}

Jaakkola, R 2022, Uniform Guarded Fragments. in P Bouyer & L Schröder (eds), Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings. Lecture Notes in Computer Science , vol. 13242 LNCS, Springer, pp. 409-427, European Joint Conferences on Theory and Practice of Software, Munich, Germany, 4/04/22. https://doi.org/10.1007/978-3-030-99253-8_21

Uniform Guarded Fragments. / Jaakkola, Reijo.
Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings. ed. / Patricia Bouyer; Lutz Schröder. Springer, 2022. p. 409-427 (Lecture Notes in Computer Science ; Vol. 13242 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Uniform Guarded Fragments

AU - Jaakkola, Reijo

PY - 2022

Y1 - 2022

N2 - In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.

AB - In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of guarded two-variable logic, has the Craig interpolation property. We will also prove that the satisfiability problem of uniform guarded fragment is NExpTime-complete.

KW - Guarded fragment

KW - Interpolation

KW - Satisfiability problem

U2 - 10.1007/978-3-030-99253-8_21

DO - 10.1007/978-3-030-99253-8_21

M3 - Conference contribution

AN - SCOPUS:85128454317

SN - 9783030992521

T3 - Lecture Notes in Computer Science

SP - 409

EP - 427

BT - Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings

A2 - Bouyer, Patricia

A2 - Schröder, Lutz

PB - Springer

T2 - European Joint Conferences on Theory and Practice of Software

Y2 - 4 April 2022 through 6 April 2022

ER -

Jaakkola R. Uniform Guarded Fragments. In Bouyer P, Schröder L, editors, Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings. Springer. 2022. p. 409-427. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-030-99253-8_21

Uniform Guarded Fragments

Abstract

Publication series

Conference

Keywords

Publication forum classification

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this