A technique for proving decidability of containment and equivalence of linear constraint queries
From MaRDI portal
Publication:1807671
DOI10.1006/jcss.1999.1624zbMath0939.68028OpenAlexW1988946128MaRDI QIDQ1807671
Publication date: 23 November 1999
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1999.1624
Related Items
Verification in loosely synchronous queue-connected discrete timed automata. ⋮ VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ ON STRONG REVERSIBILITY IN P SYSTEMS AND RELATED PROBLEMS ⋮ ON REACHABILITY AND SAFETY IN INFINITE-STATE SYSTEMS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Conjunctive query containment with respect to views and constraints
- The complexity of querying indefinite data about linearly ordered domains
- Finite-model theory -- A personal perspective
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- The comparison of the expressive power of first-order dynamic logics
- Computable queries for relational data bases
- The complexity of decision problems for finite-turn multicounter machines
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- Deterministic one-counter automata
- Reversal-bounded multipushdown machines
- Query languages for bags and aggregate functions
- Finitely representable databases
- Queries with arithmetical constraints
- Model theory
- On monadic NP vs monadic co-NP
- An application of games to the completeness problem for formalized theories
- On conjunctive queries containing inequalities
- Relational expressive power of constraint query languages
- Two-Way Counter Machines and Diophantine Equations
- A Decision Procedure for the First Order Theory of Real Addition with Order
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- An NP-Complete Number-Theoretic Problem
- Equivalences among Relational Expressions
- First-Order Queries on Finite Structures Over the Reals
- New Decidability Results Concerning Two-Way Counter Machines
- Presburger arithmetic with bounded quantifier alternation
- A relational model of data for large shared data banks
