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

program verificationdecision proceduresloops in graphs

Mathematics Subject Classification ID

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

Cited in

(17)

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

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)