Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers

DOI10.1016/j.tcs.2012.10.043zbMath1296.03013OpenAlexW2008796796MaRDI QIDQ391115

Davide Bresolin, Guido Sciavicco, Pietro Sala, Angelo Montanari

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.10.043

zbMATH Keywords

complexitydecidabilitymetric temporal logicdecision procedureinterval logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (3)

Metric propositional neighborhood logic with an equivalence relation ⋮ A separation theorem for discrete-time interval temporal logic ⋮ Bounded variability of metric temporal logic

Cites Work

• Maintaining knowledge about temporal intervals
• Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
• An optimal decision procedure for right propositional neighborhood logic
• Expressiveness and completeness of an interval tense logic
• Two variable first-order logic over ordered domains
• Metric Propositional Neighborhood Logics: Expressiveness, Decidability, and Undecidability
• Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders
• Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders
• An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic
• A Modal Logic for Chopping Intervals
• A propositional modal logic of time intervals
• A Road Map of Interval Temporal Logics and Duration Calculi

This page was built for publication: Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers