- 1.S. Abiteboul, P. Kanellakis, and G. Gtahne. Oil the representation and querying of sets of possible worlds. Theoretical Computer Science, 78:159-187, 1991. Google ScholarDigital Library
- 2.J. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26:510-521, 1983. Google ScholarDigital Library
- 3.A.K. Chandra, D.C. Kozen, and L.J. Stockmeyer. Alternation. Journal of the ACM, 28:114-133, 1981. Google ScholarDigital Library
- 4.A.K. Chandra and P.K. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proceedings of the A CM Symposium on the Theory of Computing, pages 77-90. Association for Computing Machinery, 1976. Google ScholarDigital Library
- 5.M.R. Fellows and M.A. Langston. Nonconstructive advances in polynomial time complexity. Informatzon Processing Letters, 26:157-162, 1987. Google ScholarDigital Library
- 6.M.R. Fellows and M.A. Langston. Nonconstructive tools for proving polynomial time decidability. Journal of the ACM, 35:727-739, 1988. Google ScholarDigital Library
- 7.M.C. Golumbic. Algortthm#c Graph Theory and Perfect Graphs. Academic Press, New York, 1980.Google Scholar
- 8.M.C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Technical Report RRR No. 22-91, RUT- COR: Rutgers Center for Operations Research, New Brunswick NJ, May 1991.Google Scholar
- 9.J. Halpern and Y. Shoham. A propositional modal logic of time intervals. In Proceedings of the Symposium on Logic in Computer Science, pages 279-292, 1986.Google Scholar
- 10.P.C. Kanellakis, G.M. Kuper, and P.Z. Revesz. Constraint query languages. In Proceedings of the Ninth annual SIGA CT-SIGMOD.SIGART Symposium on the Principles of Database Systems, pages 299-313, 1990. Google ScholarDigital Library
- 11.D.G. Kendall. Some methods and problems in statistical archeology. World Archeology, pages 68-76, 1969.Google Scholar
- 12.A. Klug. On conjunctive queries containing inequalities. Journal of the ACM, 35(1):146-160, 1988. Google ScholarDigital Library
- 13.J.B. Kruskal. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combznator#al Theory (Ser. A), 13:297-305, 1972.Google Scholar
- 14.J.L. Lassez. Querying constraints. In Proceedings of the Ninth annual SIGA CT-SIGMOD-SIGART Symposium on the Principles of Database Systems, pages 288-298, 1990. Google ScholarDigital Library
- 15.D. Maier. The complexity of some problems on subsequences and supersequences. Journal of the A CM, 25(2):322-336, 1978. Google ScholarDigital Library
- 16.D.J. Rosenkrantz and H.B. Hunt. Processing conjunctive predicates and queries. In Proceedings of the Swcth International Conference on Very Large Databases, pages 64-72, 1980.Google Scholar
- 17.E.D. Sacerdoti. A Structure for Plans and Behav#our. Elsevier, New York, 1977.Google Scholar
- 18.J.D. Ullman. Pmnczples of Database and Knowledge Base Systems, volume H: The New Technologies. Computer Science Press, 1989. Google ScholarDigital Library
- 19.P. van Beek and R. Cohen. Exact and approximate reasoning about temporal relations. Computatzonal Intelligence, 6(3):132-144, 1990. Google ScholarDigital Library
- 20.R. van der Meyden. Recursively indefinite databases. In S. Abiteboul and P.C. Kanellakis, editors, ICDT'90: Third International Conference on Database Theory, pages 364-378. Springer LNCS No. 470, 1990. Google ScholarDigital Library
- 21.R. van der Meyden. The Complexity of Querying Indefinite In.formation: Defined Relations, Recursion and Lznear Order. PhD thesis, Rutgers University, 1992. Google ScholarDigital Library
- 22.M. Valdi. The complexity of relational query languages. In Proceedings of the A CM Symposium on the Theory of Computing, pages 137-146, 1982. Google ScholarDigital Library
- 23.M. Vardi. Querying logical databases. Journal of Computer and System Sciences, 33:142-160, 1986. Google ScholarDigital Library
- 24.M. Vilain and H. Kautz. Constraint propagation algorithms for temporal reasoning. In AAAI: Proceedings of the National Conference zn Artificial Intelhgence, pages 377-382. Morgan Kaufinan, 1986.Google ScholarDigital Library
Index Terms
- The complexity of querying indefinite data about linearly ordered domains
Recommendations
The Complexity of Querying Indefinite Data about Linearly Ordered Domains
Special issue: dedicated to the memory of Paris KanellakisIn applications dealing with ordered domains, the available data is frequently indefinite. While the domain is actually linearly ordered, only some of the order relations holding between points in the data are known. Thus, the data provides only a ...
Constraint Preconditioners for Symmetric Indefinite Matrices
We study the eigenvalue bounds of block two-by-two nonsingular and symmetric indefinite matrices whose $(1,1)$ block is symmetric positive definite and Schur complement with respect to its $(2,2)$ block is symmetric indefinite. A constraint ...
Comments