|
|||||
|
|
Definability and decidability of binary predicates for time granularity |
|
| Authors: | Massimo Franceschet Angelo Montanari Adriano Peron Guido Sciavicco |
| Affiliation: | aDipartimento di Scienze, Università di Chieti-Pescara, Pescara, Italy;bDipartimento di Matematica e Informatica, Università di Udine, Udine, Italy;cDipartimento di Scienze Fisiche, Università di Napoli ‘Federico II’, Napoli, Italy |
| 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. |
| Keywords: | Time granularity Monadic theories Definability Decidability |
| 本文献已被 ScienceDirect 等数据库收录！ | |