A History of Satisfiability

John Franco and John Martin

In Handbook of Satisfiability, Vol. 185 Frontiers in Artificial Intelligence and Applications, Armin Biere, Marijn Huele, Hans van Maaren, Toby Walsh (eds.), 3-74, IOS Press, 2009.

Details | BibTeX

Probabilistic Analysis of Satisfiability Algorithms

John Franco

In Boolean Methods and Models, Yves Crama and Peter Hammer (eds.), Cambridge University Press, to appear.

Details | BibTeX

Workshop on Satisfiability: Assessing the Progress

John Franco, Victor Marek, Sean Weaver

U.S. Department of Defense internal publication, 2008.

Details | BibTeX

Extending existential quantification in conjunctions of BDDs

Sean Weaver and John Franco

Journal on Satisfiability, Boolean Modeling and Computation 1:89-110, IOS Press, 2006.

Details | BibTeX

Resolution Tunnels for Improved SAT Solver Performance

Michal Kouril and John Franco

Lecture Notes in Computer Science 3569:143-158, Springer, 2005

Details | BibTeX

A sharp threshold for the renamable Horn and q-Horn properties

Hervé Daudé, Nadia Creignou, and John Franco

Discrete Applied Mathematics 153:48-57, Elsevier, 2005.

Details | BibTeX

Typical case complexity of Satisfiability algorithms and the threshold phenomenon

John Franco

Discrete Applied Mathematics 153:89-123, Elsevier, 2005.

Details | BibTeX

Function-complete lookahead in support of efficient SAT search heuristics

John Franco, Michal Kouril, John S. Schlipf, Sean Weaver, Michael Dransfield, and W. Mark Vanfleet

Journal of Universal Computer Science 12(10):1655-1692, Graz University of Technology, Austria, 2004

Details | BibTeX

SBSAT: A State-Based, BDD-Based Satisfiability Solver

John Franco, Michal Kouril, John S. Schlipf, Jeffrey Ward, Sean Weaver, Michael Dransfield, and W. Mark Vanfleet

Lecture Notes in Computer Science 2919:398-410, Springer, 2004

Details | BibTeX

On good algorithms for determining unsatisfiability of propositional formulas

John Franco, Ram Swaminathan

Discrete Applied Mathematics 130(2):129-138, Elsevier, 2003.

Details | BibTeX

A perspective on certain polynomial time classes of Satisfiability

John Franco and Allen Van Gelder

Discrete Applied Mathematics 125:177-214, Elsevier, 2003.

Details | BibTeX

Algorithms for the Satisfiability (SAT) Problem

Jun Gu, Paul W. Purdom, John Franco, and Benjamin Wah

In Handbook of Applied Optimization, Panos Pardalos and M.G.C. Resende (eds.), 640-660, Oxford University Press, 2002.

Details | BibTeX

Results related to threshold phenomena research in Satisfiability: lower bounds

John Franco

Theoretical Computer Science 265:147-157, Elsevier, 2001

Details | BibTeX

Some interesting research directions in Satisfiability

John Franco

Annals of Mathematics and Artificial Intelligence 28:7-15, 2000.

Details | BibTeX

Finding optimal boolean classifiers

John Franco

In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems from the series Nonconvex Optimization and its Applications, Vol. 42, Panos Pardalos (ed.), Kluwer, 2000.

Details | BibTeX

Algorithms for the Satisfiability (SAT) Problem

Jun Gu, Paul W. Purdom, John Franco, and Benjamin Wah

In Handbook of Combinatorial Optimization, Supplement Volume A, D-Z. Du and Panos Pardalos (eds.), Kluwer, 1999.

Details | BibTeX

An algorithm for the class of pure implicational formulas

Judy Goldsmith, John S. Schlipf, Ewald Speckenmeyer, and Ram Swaminathan

Discrete Applied Mathematics 96-97:89-106, Elsevier, 1999.

Details | BibTeX

The probability of pure literals

John W. Rosenthal, Jack M. Plotkin, and John Franco

Journal of Computational Logic 9:501-513, 1999.

Details | BibTeX

Relative size of certain polynomial time solvable subclasses of satisfiability

John Franco

DIMACS Series on Discrete Mathematics and Theoretical Computer Science 35:211-224, American Mathematical Society, 1997

Details | BibTeX

Algorithms for the Satisfiability problem: a survey

Jun Gu, Paul W. Purdom, John Franco, and Benjamin Wah

DIMACS Series on Discrete Mathematics and Theoretical Computer Science 35:19-151, American Mathematical Society, 1997.

Details | BibTeX

Network servers and Java

John Franco

IEEE Potentials, 15-17, 1997.

Details | BibTeX

The brick wall: NP-completeness

John Franco

IEEE Potentials, 37-40, 1997

Details | BibTeX

Average case results for Satisfiability algorithms under the random-clause-width model

John Franco and Ram Swaminathan

Annals of Mathematics and Artificial Intelligence 20:357-391, Kluwer, 1997.

Details | BibTeX

On finding solutions to extended Horn sets

John S. Schlipf, Fred Annexstein, John Franco, and Ram Swaminathan

Information Processing Letters 54:133-137, North-Holland, 1995.

Details | BibTeX

Unique satisfiability for Horn sets can be solved in nearly linear time

Ken Berman, John Franco, and John S. Schlipf

Discrete Applied Mathematics 60:77-91, Elsevier, 1995.

Details | BibTeX

Work-preserving emulations of Shuffle-Exchange networks by linear arrays

Fred Annexstein and John Franco

Discrete Applied Mathematics 60:13-23, 1995.

Details | BibTeX

Computing the well-founded semantics faster

Ken Berman, John Franco, and John S. Schlipf

Lecture Notes in Computer Science, 928:113-126, 1995.

Details | BibTeX

Analysis of constant head wells using instantaneous source functions

John Franco and Larry Murdoch

Water Resources Research 30:117-124, 1994.

Details | BibTeX

On the occurrence of null clauses in random instances of satisfiability

John Franco

Discrete Applied Mathematics 41:203-209, Elsevier, 1993.

Details | BibTeX

The Scheme Programming Language

Olivier Danvy, John Franco, and Daniel P. Friedman

In A Comparative Study of Parallel Programming Languages: The Salishan Problems, John Feo (ed.), Elsevier, 1992.

Details | BibTeX

Recent work at the interface of logic, combinatorics, and computer science

John Franco, J. Michael Dunn, and William H. Wheeler

extended preface to the special issue of Annals of Mathematics and Artificial Intelligence on logic and combinatorics, 6:1-16, Kluwer, 1992.

Details | BibTeX

Probabilistic analysis of algorithms for stuck-at test generation in PLAs

John Franco

Lecture Notes in Control and Information Sciences, 174:56-75, Springer, 1992.

Details | BibTeX

Average case analysis of hashing with lazy deletions

Pedro Celis and John Franco

Information Sciences, 62:13-26, North-Holland, 1992.

Details | BibTeX

Elimination of infrequent variables improves average case performance of Satisfiability algorithms

John Franco

SIAM Journal on Computing, 20:1119-1127, 1991.

Details | BibTeX

Multi-way Streams in Scheme

John Franco, Daniel P. Friedman, and Steven D. Johnson

Computer Languages, 15:109-125, Pergamon Press, 1990.

Details | BibTeX

Costs of quadtree representation of non-dense matrices

David Wise and John Franco

Journal on Parallel and Distributed Computing 9:282-296, 1990.

Details | BibTeX

Towards a facility for lexically scoped, dynamic mutual recursion in Scheme

John Franco and Daniel P. Friedman

Computer Languages, 15:55-64, Pergamon Press, 1990.

Details | BibTeX

Probabilistic analysis of a generalization of the unit-clause literal selection heuristic for the k-satisfiability problem

Min-Teh Chao and John Franco

Information Sciences, 51:289-314, North-Holland, 1990.

Details | BibTeX

Creating efficient programs by exchanging data for procedures

John Franco and Daniel P. Friedman

Computer Languages, 14:11-23, Pergamon Press, 1989.

Details | BibTeX

Probabilistic performance of a heuristic for the satisfiability problem

John Franco and Y.C. Ho

Discrete Applied Mathematics, 22:35-51, Elsevier, 1988/1989.

Details | BibTeX

Correction to probabilistic analysis of the Davis-Putnam Procedure for solving the Satisfiability problem

Jack M. Plotkin, John W. Rosenthal, and John Franco

Discrete Applied Mathematics, 17:295-299, Elsevier, 1987.

Details | BibTeX

On the probabilistic performance of algorithms for the Satisfiability problem

John Franco

Information Processing Letters, 23:103-106, North-Holland, 1986.

Details | BibTeX

Probabilistic analysis of two heuristics for the 3-Satisfiability problem

Min-Teh Chao and John Franco

SIAM Journal on Computing, 15:1106-1118, 1986.

Details | BibTeX

An approximation algorithm for the maximum independent set problem in cubic planar graphs

Elarby Choukhmane and John Franco

Networks, 16:349-356, 1986.

Probabilistic analysis of the pure literal heuristic

John Franco

Annals of Operations Research, 1:273-289, 1984.

Details | BibTeX

Probabilistic analysis of the Davis-Putnam procedure for solving the satisfiability problem

John Franco and Marvin Paull

Discrete Applied Mathematics 5:77-87, Elsevier, 1983.

Details | BibTeX