Decidability of a Hybrid Duration Calculus | Zendy

Thomas Bolander | Zendy; Jens Ulrik Hansen | Zendy; Michael R. Hansen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Decidability of a Hybrid Duration Calculus

Author(s) -

Thomas Bolander,

Jens Ulrik Hansen,

Michael R. Hansen

Publication year - 2007

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2006.11.029

Subject(s) - decidability , satisfiability , mathematics , boolean satisfiability problem , calculus (dental) , duration (music) , expressive power , discrete mathematics , computer science , algorithm , programming language , physics , medicine , dentistry , acoustics

We present a logic which we call Hybrid Duration Calculus (HDC). HDC is obtained by adding the following hybrid logical machinery to the Restricted Duration Calculus (RDC): nominals, satisfaction operators, down-arrow binder, and the global modality. RDC is known to be decidable, and in this paper we show that decidability is retained when adding the hybrid logical machinery. Decidability of HDC is shown by reducing the satisfiability problem to satisfiability of Monadic Second-Order Theory of Order. We illustrate the increased expressive power obtained in hybridizing RDC by showing that HDC, in contrast to RDC, can express all of the 13 possible relations between intervals

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research