In this paper we study the definability and decidability of binary predicates for time granularity in monadic languages interpreted over finitely and infinitely layered structures. We focus our attention on the equi-level (respectively equi-column) predicate constraining two time points to belong to the same layer (respectively column) and on the horizontal (respectively vertical) successor predicate relating a time point to its successor within a given layer (respectively column). We give a number of positive and negative results by reduction to/from a wide spectrum of decidable/undecidable problems.
Definability and decidability of binary predicates for time granularity
FRANCESCHET, Massimo;MONTANARI, Angelo;SCIAVICCO, Guido
2006-01-01
Abstract
In this paper we study the definability and decidability of binary predicates for time granularity in monadic languages interpreted over finitely and infinitely layered structures. We focus our attention on the equi-level (respectively equi-column) predicate constraining two time points to belong to the same layer (respectively column) and on the horizontal (respectively vertical) successor predicate relating a time point to its successor within a given layer (respectively column). We give a number of positive and negative results by reduction to/from a wide spectrum of decidable/undecidable problems.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
jal2.pdf
non disponibili
Tipologia:
Altro materiale allegato
Licenza:
Non pubblico
Dimensione
287.96 kB
Formato
Adobe PDF
|
287.96 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.