Feasibility checking in Horn constraint systems through a reduction based approach

DOI10.1016/j.tcs.2014.12.016zbMath1312.68231OpenAlexW2019254635MaRDI QIDQ2344728

James Worthington, K. Subramani and Vahan Mkrtchyan

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 algorithmlinear feasibilitydifference constraintsHorn constraintslattice point feasibility

Mathematics Subject Classification ID

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

Related Items (4)

Exact and parameterized algorithms for read-once refutations in Horn constraint systems ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Integer feasibility and refutations in UTVPI constraints using bit-scaling ⋮ Trichotomy for the reconfiguration problem of integer linear systems

Uses Software

• Yices

Cites Work

• The octagon abstract domain
• Box invariance in biologically-inspired dynamical systems
• The Mailman algorithm: a note on matrix-vector multiplication
• Symmetric space-bounded computation
• Simplicial pivoting algorithms for a tractable class of integer programs
• Fourier-Motzkin elimination and its dual
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A Combinatorial Algorithm for Horn Programs
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Renaming a Set of Clauses as a Horn Set
• Scaling Algorithms for the Shortest Paths Problem
• Automated Reasoning
• Frontiers of Combining Systems
• Computer Aided Verification
• Fast and Flexible Difference Constraint Propagation for DPLL(T)
• Tractable constraints on ordered domains
• Computability and complexity theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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