Generalizing Allen's Theory of Time to Tree-Like Structures

Date

2015-09-25

Author

Durhan, Salih
Sciavicco, Guido

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

133
views

0
downloads

Allen's Interval Algebra is one of the most prominent formalisms in the area of qualitative temporal (and, by extension, spatial) reasoning. However, its applications are naturally restricted to linear flows of time. While there is some recent work focused on studying relations between intervals (and also between intervals and points) on branching structures, there is no rigorous study of the first-order theory of branching time. In this paper, we approach this problem under a very general definition of time structures as tree-like lattices. Allen's representation theorem shows that meets is expressively complete for the class of all unbounded linear orders, and it is easy to see that it is also complete for the class of all linear orders. Here we prove that, surprisingly, meets remains complete for the class of all unbounded tree-like lattices, and we provide an easy axiomatization of the class of all unbounded tree-like lattices in the branching language. Then, we show that meets becomes incomplete in the class of all tree-like lattices; we give a minimal complete set of three relations for this case along with an axiomatization, which turns out to be particularly challenging to obtain.

Subject Keywords

Representation Theorems, Branching time

URI

https://hdl.handle.net/11511/65564

DOI

https://doi.org/10.1109/time.2015.17

Collections

Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

On equivelar triangulations of surfaces Adıgüzel, Ebru; Pamuk, Semra; Department of Mathematics (2018) Persistent homology is an algebraic method for understanding topological features of discrete objects or data (finite set of points with metric defined on it). In algebraic topology, the Mayer Vietoris sequence is a powerful tool which allows one to study the homology groups of a given space in terms of simpler homology groups of its subspaces. In this thesis, we study to what extent does persistent homology benefit from Mayer Vietoris sequence.
Optimization of the array geometry for direction finding Özaydın, Seval; Koç, Seyit Sencer; Tanık, Yalçın; Department of Electrical and Electronics Engineering (2003) In this thesis, optimization of the geometry of non-uniform arrays for direction finding yielding unambiguous results is studied. A measure of similarity between the array response vectors is defined. In this measure, the effects of antenna array geometry, source placements and antenna gains are included as variable parameters. Then, assuming that the antenna gains are known and constant, constraints on the similarity function are developed and described to result in unambiguous configurations and maximum r...
Development of an incompressible navier-stokes solver with alternating cell direction implicit method on structured and unstructured quadrilateral grids Baş, Onur; Tuncer, İsmail Hakkı; Department of Aerospace Engineering (2007) In this research, the Alternating Cell Direction Implicit method is used in temporal discretisation of the incompressible Navier-Stokes equations and compared with the well known and widely used Point Gauss Seidel scheme on structured and quadrilateral unstructured meshes. A two dimensional, laminar and incompressible Navier-Stokes solver is developed for this purpose using the artificial compressibility formulation. The developed solver is used to obtain steady-state solutions with implicit time stepping m...
Studies on non-weakly regular bent functions and related structures Pelen, Rumi Melih; Özbudak, Ferruh; Department of Mathematics (2020) Interest in bent functions over finite fields arises both from mathematical theory and practical applications. There has been lots of literature addressing various properties of bent functions. They have a number of applications consisting of coding theory, cryptography, and sequence designs. They’re divided into four subclasses: regular bent functions that are contained within the class of weakly regular bent functions that are contained within the class of dual-bent functions. Additionally, there are non-...
Approximate analytical solutions of the pseudospin symmetric Dirac equation for exponential-type potentials Arda, Altu; Sever, Ramazan; TEZCAN, CEVDET (Wiley, 2009-10-01) The solvability of The Dirac equation is studied for the exponential-type potentials with the pseudospin symmetry by using the parametric generalization of the Nikiforov-Uvarov method. The energy eigenvalue equation, and the corresponding Dirac spinors for Morse, Hulthen, and q-deformed Rosen-Morse potentials are obtained within the framework of an approximation to the spin-orbit coupling term, so the solutions are given for any value of the spin-orbit quantum number kappa = 0, or kappa not equal 0. (C) 200...

Citation Formats

S. Durhan and G. Sciavicco, “Generalizing Allen’s Theory of Time to Tree-Like Structures,” 2015, p. 69, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65564.