Monodic Fragments of Probabilistic First-order Logic

Jung JC, Lutz C, Goncharov S, Schröder L (2014)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2014

Publisher: Springer

Edited Volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Series: Lecture Notes in Computer Science

City/Town: Berlin/Heidelberg

Book Volume: 8573

Pages Range: 256-267

Conference Proceedings Title: Proc. 41st International Colloquium on Automata, Languages, and Programming

Event location: Kopenhagen

ISBN: 978-3-662-43951-7

URI: http://www.informatik.uni-bremen.de/tdki/research/papers/2014/JLGS-ICALP14.pdf

DOI: 10.1007/978-3-662-43951-7_22

Abstract

By classical results of Abadi and Halpern, validity for probabilistic first-order logic of type 2 (ProbFO) is Π1 2-complete and thus not recursively enumerable, and even small fragments of ProbFO are undecidable. In temporal first-order logic, which has similar computational properties, these problems have been addressed by imposing monodicity, that is, by allowing temporal operators to be applied only to formulas with at most one free variable. In this paper, we identify a monodic fragment of ProbFO and show that it enjoys favorable computational properties. Specifically, the valid sentences of monodic ProbFO are recursively enumerable and a slight variation of Halpern's axiom system for type-2 ProbFO on bounded domains is sound and complete for monodic ProbFO. Moreover, decidability can be obtained by restricting the FO part of monodic ProbFO to any decidable FO fragment. In some cases, which notably include the guarded fragment, our general constructions result in tight complexity bounds. © 2014 Springer-Verlag.

Authors with CRIS profile

Sergey Goncharov Lehrstuhl für Informatik 8 (Theoretische Informatik) Lutz Schröder Lehrstuhl für Informatik 8 (Theoretische Informatik)

Related research project(s)

Probabilistische Beschreibungslogik als Fragment der Probabilistischen Logik Erster Stufe (ProbDL) April 1, 2011 - April 1, 2014

Involved external institutions

Universität Bremen DE Germany (DE)

How to cite

APA:

Jung, J.C., Lutz, C., Goncharov, S., & Schröder, L. (2014). Monodic Fragments of Probabilistic First-order Logic. In Proc. 41st International Colloquium on Automata, Languages, and Programming (pp. 256-267). Kopenhagen: Berlin/Heidelberg: Springer.

MLA:

Jung, Jean Christoph, et al. "Monodic Fragments of Probabilistic First-order Logic." Proceedings of the ICALP 2014, Kopenhagen Berlin/Heidelberg: Springer, 2014. 256-267.

BibTeX: Download