Expressiveness of Hybrid Temporal Logic on Data Words | Zendy

Ahmet Kara | Zendy; Thomas Schwentick | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Expressiveness of Hybrid Temporal Logic on Data Words

Author(s) -

Ahmet Kara,

Thomas Schwentick

Publication year - 2011

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.2011.10.010

Subject(s) - succinctness , quantifier (linguistics) , computer science , temporal logic , linear temporal logic , automaton , variable (mathematics) , expressive power , theoretical computer science , artificial intelligence , mathematics , mathematical analysis

Hybrid temporal logic (HTL) on data words can be considered as an extension of the logic LTL↓ introduced by Demri and Lazic [Stephane Demri and Ranko Lazic. LTL with the freeze quantifier and register automata. In LICSʼ06: Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science, pages 17–26, Washington, DC, USA, 2006. IEEE Computer Society]. The paper compares the expressive power of HTL on data words with that of LTL↓. It is shown that there are properties of data words that can be expressed in HTL with two variables but not in LTL↓. On the other hand, every property that can be expressed in HTL with one variable can also be expressed in LTL↓ with one variable. The paper further studies the succinctness of HTL in comparison with LTL↓ and shows that the number-of-variables hierarchy of HTL is infinite

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