|
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.
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.
Details
|
BibTeX
|
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
|
|
|
|