English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we investigate the model checking (MC) problem for Halpern andShoham's interval temporal logic HS. In the last years, interval temporal logicMC has received an increasing attention as a viable alternative to thetraditional (point-based) temporal logic MC, which can be recovered as aspecial case. Most results have been obtained under the homogeneity assumption,that constrains a proposition letter to hold over an interval if and only if itholds over each component state. Recently, Lomuscio and Michaliszyn proposed away to relax such an assumption by exploiting regular expressions to define thebehaviour of proposition letters over intervals in terms of their componentstates. When homogeneity is assumed, the exact complexity of MC is a difficultopen question for full HS and for its two syntactically maximal fragmentsAA'BB'E' and AA'EB'E'. In this paper, we provide an asymptotically optimalbound to the complexity of these two fragments under the more expressivesemantic variant based on regular expressions by showing that their MC problemis AEXP_pol-complete, where AEXP_pol denotes the complexity class of problemsdecided by exponential-time bounded alternating Turing Machines making apolynomially bounded number of alternations.

On the Complexity of Model Checking for Syntactically Maximal Fragments of the Interval Temporal Logic HS with Regular Expressions