On-line algorithms for polynomially solvable satisfiability problems

DOI10.1016/0743-1066(91)90006-BMaRDI QIDQ3970696zbMATH OpenDBLPWikidataFDO

Authors Giuseppe F. Italiano, Giorgio Ausiello

Publication date 25 June 1992

Published in The Journal of Logic Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0743-1066(91)90006-B

zbMATH Keywords

complexitysatisfiability problemdirected hypergraphon-line decision algorithmspropositional Horn formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Decidability of theories and sets of sentences (03B25) Mechanization of proofs and logical operations (03B35)

Recommendations

• On-line algorithms for satisfiability problems with uncertainty
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Solving the incremental satisfiability problem
• Algorithms for testing the satisfiability of propositional formulae

Cited in

(15)

• Dynamic maintenance of directed hypergraphs
• On the complexity of strongly connected components in directed hypergraphs
• Non-oblivious local search for graph and hypergraph coloring problems
• Partially dynamic maintenance of minimum weight hyperpaths
• The incremental satisfiability problem for a two conjunctive normal form
• Fully dynamic biconnectivity in graphs
• On Online Labeling with Polynomially Many Labels
• Fuzzy logic programs as hypergraphs. Termination results
• Sensitivity analysis for Horn formulae
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• On-line algorithms for satisfiability problems with uncertainty
• Linear time analysis of properties of conflict-free and general Petri nets
• On-line algorithms for satisfiability problems with uncertainty
• MedleySolver: online SMT algorithm selection
• Hierarchies of polynomially solvable satisfiability problems

This page was built for publication: On-line algorithms for polynomially solvable satisfiability problems

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