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

DOI10.1006/JCSS.1999.1624zbMATH Open0939.68028OpenAlexW1988946128MaRDI QIDQ1807671FDOQ1807671

Authors: Oscar H. Ibarra, Jianwen Su 

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

Recommendations

• scientific article; zbMATH DE number 1836416
• Publication:4508935
• Conjunctive query containment with respect to views and constraints
• Queries with arithmetical constraints
• scientific article; zbMATH DE number 1951561

zbMATH Keywords

counter machinesqueries

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

• Title not available (Why is that?)
• Computable queries for relational data bases
• Reversal-bounded multipushdown machines
• Model theory
• A Decision Procedure for the First Order Theory of Real Addition with Order
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• A relational model of data for large shared data banks
• Title not available (Why is that?)
• Finite-model theory -- A personal perspective
• The complexity of querying indefinite data about linearly ordered domains
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Title not available (Why is that?)
• On monadic NP vs monadic co-NP
• An application of games to the completeness problem for formalized theories
• Title not available (Why is that?)
• On conjunctive queries containing inequalities
• Equivalences among Relational Expressions
• Title not available (Why is that?)
• The complexity of decision problems for finite-turn multicounter machines
• Conjunctive query containment with respect to views and constraints
• New Decidability Results Concerning Two-Way Counter Machines
• Title not available (Why is that?)
• Presburger arithmetic with bounded quantifier alternation
• Title not available (Why is that?)
• Deterministic one-counter automata
• A closed-form evaluation for Datalog queries with integer (gap)-order constraints
• Finitely representable databases
• Queries with arithmetical constraints
• Relational expressive power of constraint query languages
• First-Order Queries on Finite Structures Over the Reals
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• An NP-Complete Number-Theoretic Problem
• The comparison of the expressive power of first-order dynamic logics
• Query languages for bags and aggregate functions
• Two-Way Counter Machines and Diophantine Equations
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• On reachability and safety in infinite-state systems
• Verification in loosely synchronous queue-connected discrete timed automata.
• Title not available (Why is that?)
• VERIFICATION IN QUEUE-CONNECTED MULTICOUNTER MACHINES
• On strong reversibility in P systems and related problems
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES

This page was built for publication: A technique for proving decidability of containment and equivalence of linear constraint queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1807671)