Monodic Fragments of Probabilistic First-order Logic
Author(s): Jung J, Lutz C, Goncharov S, Schröder L
Title edited volumes: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publishing place: Berlin/Heidelberg
Publication year: 2014
Title of series: Lecture Notes in Computer Science
Conference Proceedings Title: Proc. 41st International Colloquium on Automata, Languages, and Programming
Pages range: 256-267
Event: ICALP 2014
Event location: Kopenhagen
Start date of the event: 08/07/2014
End date of the event: 11/07/2014
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.
FAU Authors / FAU Editors How to cite
APA: Jung, J., 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). 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.