Metric Propositional Neighborhood Logics: Expressiveness, Decidability, and Undecidability

Davide Bresolin, Dario Della Monica, Valentin Goranko, Angelo Montanari, Guido Sciavicco

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    Interval temporal logics formalize reasoning about interval structures over (usually) linearly ordered domains, where time intervals are the primitive ontological entities and truth of formulae is defined relative to time intervals, rather than time points. In this paper, we introduce and study Metric Propositional Neighborhood Logic (MPNL) over natural numbers. MPNL features two modalities referring, respectively, to an interval that is “met by” the current one and to an interval that “meets” the current one, plus an infinite set of length constraints, regarded as atomic propositions, to constrain the lengths of intervals. We argue that MPNL can be successfully used in different areas of artificial intelligence to combine qualitative and quantitative interval temporal reasoning, thus providing a viable alternative to well-established logical frameworks such as Duration Calculus. We show that MPNL is decidable in double exponential time and expressively complete with respect to a well-defined subfragment of the two-variable fragment FO2[N, =,
    Original languageEnglish
    Title of host publicationProceedings of the 19th European Conference on Artificial Intelligence (ECAI'10)
    EditorsMichael Wooldridge
    Publication date2010
    Pages695-700
    ISBN (Print)978-1-60750-605-8
    DOIs
    Publication statusPublished - 2010
    Event19th European Conference on Artificial Intelligence - Lisbon
    Duration: 1 Jan 2010 → …

    Conference

    Conference19th European Conference on Artificial Intelligence
    CityLisbon
    Period01/01/2010 → …
    SeriesFrontiers in Artificial Intelligence and Applications
    Number215
    ISSN0922-6389

    Cite this

    Bresolin, D., Della Monica, D., Goranko, V., Montanari, A., & Sciavicco, G. (2010). Metric Propositional Neighborhood Logics: Expressiveness, Decidability, and Undecidability. In M. Wooldridge (Ed.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI'10) (pp. 695-700). Frontiers in Artificial Intelligence and Applications, No. 215 https://doi.org/10.3233/978-1-60750-606-5-695