Feasibility checking in Horn constraint systems through a reduction based approach

DOI10.1016/J.TCS.2014.12.016MaRDI QIDQ2344728zbMATH OpenOpenAlexFDO

Authors J. Worthington, K. Subramani

Publication date 18 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.12.016

zbMATH Keywords

combinatorial algorithmdifference constraintsHorn constraintslattice point feasibilitylinear feasibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27)

Recommendations

• A new algorithm for linear and integer feasibility in Horn constraints
• A combinatorial algorithm for Horn programs
• A combinatorial algorithm for Horn programs
• On a generalization of Horn constraint systems
• Analyzing fractional Horn constraint systems

Cites work

• A combinatorial algorithm for Horn programs
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Automated Reasoning
• Box invariance in biologically-inspired dynamical systems
• Computability and complexity theory
• Computer Aided Verification
• Fast and Flexible Difference Constraint Propagation for DPLL(T)
• Fourier-Motzkin elimination and its dual
• Frontiers of Combining Systems
• scientific article; zbMATH DE number 43398 (Why is no real title available?)
• scientific article; zbMATH DE number 2090312 (Why is no real title available?)
• Introduction to algorithms
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On solving Boolean combinations of UTVPI constraints.
• Renaming a Set of Clauses as a Horn Set
• Scaling Algorithms for the Shortest Paths Problem
• Simplicial pivoting algorithms for a tractable class of integer programs
• Symmetric space-bounded computation
• The Mailman algorithm: a note on matrix-vector multiplication
• The octagon abstract domain
• Tractable constraints on ordered domains

Cited in

(7)

• Exact and parameterized algorithms for read-once refutations in Horn constraint systems
• Analyzing fractional Horn constraint systems
• A combinatorial algorithm for Horn programs
• Analyzing read-once cutting plane proofs in Horn systems
• Integer feasibility and refutations in UTVPI constraints using bit-scaling
• A new algorithm for linear and integer feasibility in Horn constraints
• A combinatorial algorithm for Horn programs

Describes a project that uses

Uses Software

• Yices

This page was built for publication: Feasibility checking in Horn constraint systems through a reduction based approach

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