@incollection{Koubarakis:PKRR:1994,
    Abstract = {We study the complexity of quantifier elimination and decision in first-order theories of temporal constraints. With the exception of Ladkin, AI researchers have largely ignored this problem. We consider the first-order theories of point and interval constraints over two time structures: the integers and the rational. We show that in all cases quantifier-elimination can be done in PSPACE. We also show that the decision problem for arbitrarily quantified sentences is PSPACE-complete while for ∃k sentences it is ∑pk-complete. Our results must be of interest to researchers working on temporal constraints, computational complexity of logical theories, constraint databases and constraint logic programming.},
    Author = {Koubarakis, Manolis},
    BookTitle = {Principles of Knowledge Representation and Reasoning},
    Editor = {Doyle, Jon and Sandewall, Erik and Torasso, Pietro},
    File = {kr94 (0) - a - a - h.pdf},
    ISSN = {10469567},
    Pages = {379 - 390},
    Publisher = {Morgan Kaufmann},
    Series = {The Morgan Kaufmann Series in Representation and Reasoning},
    Title = {Complexity Results for First-Order Theories of Temporal Constraints},
    URL = {http://www.sciencedirect.com/science/article/pii/B9781483214528501317},
    Year = {1994},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/B9781483214528501317},
    bdsk-url-2 = {https://doi.org/10.1016/B978-1-4832-1452-8.50131-7},
    date-added = {2019-04-29 13:25:19 +0200},
    date-modified = {2019-04-29 14:39:25 +0200},
    doi = {10.1016/B978-1-4832-1452-8.50131-7}
}

@incollection{Koubarakis:PKRR:1994, Abstract = {We study the complexity of quantifier elimination and decision in first-order theories of temporal constraints. With the exception of Ladkin, AI researchers have largely ignored this problem. We consider the first-order theories of point and interval constraints over two time structures: the integers and the rational. We show that in all cases quantifier-elimination can be done in PSPACE. We also show that the decision problem for arbitrarily quantified sentences is PSPACE-complete while for ∃k sentences it is ∑pk-complete. Our results must be of interest to researchers working on temporal constraints, computational complexity of logical theories, constraint databases and constraint logic programming.}, Author = {Koubarakis, Manolis}, BookTitle = {Principles of Knowledge Representation and Reasoning}, Editor = {Doyle, Jon and Sandewall, Erik and Torasso, Pietro}, File = {kr94 (0) - a - a - h.pdf}, ISSN = {10469567}, Pages = {379 - 390}, Publisher = {Morgan Kaufmann}, Series = {The Morgan Kaufmann Series in Representation and Reasoning}, Title = {Complexity Results for First-Order Theories of Temporal Constraints}, URL = {http://www.sciencedirect.com/science/article/pii/B9781483214528501317}, Year = {1994}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/B9781483214528501317}, bdsk-url-2 = {https://doi.org/10.1016/B978-1-4832-1452-8.50131-7}, date-added = {2019-04-29 13:25:19 +0200}, date-modified = {2019-04-29 14:39:25 +0200}, doi = {10.1016/B978-1-4832-1452-8.50131-7} }