Deciding Linear Inequalities by Computing Loop Residues

DOI10.1145/322276.322288MaRDI QIDQ3922186zbMATH OpenOpenAlexWikidataFDO

Authors Robert E. Shostak

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322276.322288

zbMATH Keywords

decision proceduresloops in graphsprogram verification

Mathematics Subject Classification ID

Linear inequalities of matrices (15A39) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05)

Cited in

(17)

• Constraint propagation with interval labels
• Temporal constraint networks
• Testing the necklace condition for shortest tours and optimal factors in the plane
• Querying temporal and spatial constraint networks in PTIME
• Queries on ontologies with temporal dependences on Allen's extended interval logic
• Weak monotonicity and Bayes-Nash incentive compatibility
• A class of polynomially solvable range constraints for interval analysis without widenings
• Bounded model checking for timed automata
• Injective convex polyhedra
• The dial-A-ride problem with transfers
• Better abstractions for timed automata
• The Linear Complementarity Problems with a Few Variables per Constraint
• Log-linear dynamics and local potential
• A Logic of East and West
• Triangulations with Circular Arcs
• The two variable per inequality abstract domain
• A set partitioning reformulation of a school bus scheduling problem

This page was built for publication: Deciding Linear Inequalities by Computing Loop Residues

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