University of Cincinnati Logo
 

 
COMPUTER SCIENCE
THEORY and ALGORITHMS

Publications

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.

Probabilistic Analysis of Satisfiability Algorithms

John Franco

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

Workshop on Satisfiability: Assessing the Progress

John Franco, Victor Marek, Sean Weaver

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

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.

Resolution Tunnels for Improved SAT Solver Performance

Michal Kouril and John Franco

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

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.

Typical case complexity of Satisfiability algorithms and the threshold phenomenon

John Franco

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

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

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

On good algorithms for determining unsatisfiability of propositional formulas

John Franco, Ram Swaminathan

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

A perspective on certain polynomial time classes of Satisfiability

John Franco and Allen Van Gelder

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

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.

Results related to threshold phenomena research in Satisfiability: lower bounds

John Franco

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

Some interesting research directions in Satisfiability

John Franco

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

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.

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.

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.

The probability of pure literals

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

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

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

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.

Network servers and Java

John Franco

IEEE Potentials, 15-17, 1997.

The brick wall: NP-completeness

John Franco

IEEE Potentials, 37-40, 1997

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.

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.

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.

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

Fred Annexstein and John Franco

Discrete Applied Mathematics 60:13-23, 1995.

Computing the well-founded semantics faster

Ken Berman, John Franco, and John S. Schlipf

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

Analysis of constant head wells using instantaneous source functions

John Franco and Larry Murdoch

Water Resources Research 30:117-124, 1994.

On the occurrence of null clauses in random instances of satisfiability

John Franco

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

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.

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.

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.

Average case analysis of hashing with lazy deletions

Pedro Celis and John Franco

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

Elimination of infrequent variables improves average case performance of Satisfiability algorithms

John Franco

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

Multi-way Streams in Scheme

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

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

Costs of quadtree representation of non-dense matrices

David Wise and John Franco

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

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.

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.

Creating efficient programs by exchanging data for procedures

John Franco and Daniel P. Friedman

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

Probabilistic performance of a heuristic for the satisfiability problem

John Franco and Y.C. Ho

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

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.

On the probabilistic performance of algorithms for the Satisfiability problem

John Franco

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

Probabilistic analysis of two heuristics for the 3-Satisfiability problem

Min-Teh Chao and John Franco

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

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.

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.

ERC
MainStreet
Paul Erdos
NIT
Ladies on Campus
Oscar Robinson