Abstract | ||
---|---|---|
In this paper we study the definability and decidability of binary predicates for time granularity with respect to monadic theories over finitely and infinitely layered structures. We focus our attention on the equi-level (resp. equicolumn) predicate constraining two time points to belong to the same layer (resp. column) and on the horizontal (resp. vertical) successor predicate relating a time point to its successor within a given layer (resp. column). We give a number of positive and negative results by reduction to/from a wide spectrum of decidable/undecidable problems. |
Year | DOI | Venue |
---|---|---|
2003 | 10.1109/TIME.2003.1214896 | TIME-ICTL 2003: 10TH INTERNATIONAL SYMPOSIUM ON TEMPORAL REPRESENTATION AND REASONING AND FOURTH INTERNATIONAL CONFERENCE ON TEMPORAL LOGIC, PROCEEDINGS |
Keywords | Field | DocType |
decidability,monadic theories,definability,time granularity,formal specification,formal specifications,logic,bismuth,automata,artificial intelligence,data mining,temporal logic,databases,spectrum | Computer science,Successor cardinal,Theoretical computer science,Decidability,Temporal logic,Predicate (grammar),Granularity,Monad (functional programming),Binary number,Undecidable problem | Conference |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Massimo Franceschet | 1 | 658 | 39.91 |
Angelo Montanari | 2 | 1535 | 135.04 |
Adriano Peron | 3 | 381 | 45.82 |
Guido Sciavicco | 4 | 622 | 50.35 |