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

complexitydirected hypergraphon-line decision algorithmspropositional Horn formulasatisfiability problem

Mathematics Subject Classification ID

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

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)

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

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)