A technique for proving decidability of containment and equivalence of linear constraint queries

DOI10.1006/jcss.1999.1624zbMath0939.68028OpenAlexW1988946128MaRDI QIDQ1807671

Jianwen Su, Oscar H. Ibarra

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

zbMATH Keywords

counter machinesqueries

Mathematics Subject Classification ID

Database theory (68P15)

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