Monodic fragments of probabilistic first-order temporal logic with bounded semantics
We extend (type-2) probabilistic first-order logic with temporal operators, interpreted over fixed-length initial segments of (discrete) time. Given a formula φ of the resulting logic and a natural number N, we ask: is φ satisfiable over a space of length <i>N </i>+ 1 sequences of states (first-order structures)? We show the problem to be decidable for monodic fragments of the logic whose first-order part has a decidable satisfiability problem and we also establish the problem's computational complexity when the first-order part is among some well-known decidable fragments of first-order logic.
Authors
- Clare Dixon (ORCID: https://orcid.org/0000-0002-4610-9533)
- Georgios Kourtis (ORCID: https://orcid.org/0000-0001-9635-0643)
- Michael Fisher (ORCID: https://orcid.org/0000-0002-0875-3862)
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2025-05-15
- DOI
- https://doi.org/10.1016/j.tcs.2025.115319
- Primary Topic
- Logic, Reasoning, and Knowledge
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- UK Research and Innovation
- Royal Academy of Engineering
- Engineering and Physical Sciences Research Council