Bibliography of Papers Traceable to Special Year On Logic and Algorithms
Compiled by Christine Houck - April 1998
References
M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi, S. Rudich. Reducing the complexity of Reductions. Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC'97), 1997, pages 730-738
M. Agrawal, E. Allender, S. Rudich. Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. J. Computer and System Sciences, (special issue containing selected papers from the 11th IEEE Conference on Computational Complexity, to appear
E. Allender and K.-J. Lange. RUSPACE(log n) is contained in DSPACE(log^2 n/loglog n). Theory of Computing Systems, (special issue containing selected papers from the 7th Annual International Symposium on Algorithms and Computation (ISACC'96), to appear
E. Allender and K.-J. Lange. StUSPACE(log n) is contained in DSPACE(log^2 n/loglog n). Proceedings of the 7th Annual International Symposium on Algorithms and Computation (ISAAC'96), Lecture Notes in Computer Science 1178, 1996, Springer-Verlag, pages 193-202
R. Alur and T.A. Henzinger. Modularity for times and hybrid systems. Proceedings of the 8th International Conference on Concurrency Theory (CONCUR'97), 1997
R. Alur, K.L. McMillan, D.A. Peled. Model-checking of correctness conditions for concurrent objects. Proceedings of the 11th IEEE Symposium on Logic in Computer Science (LICS'96), 1996, pages 219-228
P.W. Beame, S.R. Buss, eds. Proof Complexity and Feasible Arithmetics, DIMACS Workshop, April 21-24, 1996, American Mathematical Society, 1997, to appear
S. Bloch. On parallel hierarchies and R^i_k. Annals of Pure and Applied Logic 89, 1997, pages 231-273
M.P. Bonacina and J. Hsiang. On the modelling of search in theorem proving -- Towards a theory of strategy analysis. Technical Report, Department of Computer Science, The University of Iowa, December 1995.
M.P. Bonacina and J. Hsiang. On the representation of dynamic search spaces in theorem proving. Proc. Int'l Computer Symposium, Kaohshiung, Taiwan, R.O.C., December 1996, pages 85-94.
M.P. Bonacina and J. Hsiang. On the notion of complexity of search in theorem proving. Logic Colloquium 1996, San Sebastian, Spain, July 1996 and Bulletin of Symbolic Logic, 3(2):253-254, June 1997.
M.L. Bonet, C. Phillips, T. Warnow, S. Yooseph. Constructing Evolutionary Trees in the Presence of Polymorphic Characters. Proceedings of the 28th Annual Symposium on the Theory of Computing (STOC'96), May 1996, pages 220-229. Also accepted for publication in the SIAM Journal of Computing
M.L. Bonet, T. Pitassi, R. Raz. No Feasible Interpolation for TC^0-Frege Proofs. Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS'97), October 1997, pages 254-265
R.B. Boppana and J.F. Lynch, eds. Logic and Random Structures, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 33, American Mathematical Society, 1997
K.B. Bruce, P.G. Kolaitis, D.M. Leivant, M.Y. Vardi. Panel - Logic in the computer science curriculum. Proceedings of the 29th ACM Symposium on Computer Science Education, 1998, pages 37--377.
S.R. Buss.``Bounded arithmetic and propositional proof complexity.'' Logic of Computation, H. Schwichtenberg, ed., Springer-Verlag, 1997, pages 67-122
S.R. Buss.``Bounded arithmetic, cryptography and complexity.'' To appear in Theoria
S.R. Buss. ``Lower bounds on Nullstellensatz proofs via designs.'' Proof Complexity and Feasible Arithmetics, DIMACS Workshop, April 21-24, 1996, P.W. Beame and S.R. Buss, eds., American Mathematical Society, 1997, pages 59-73
S.R. Buss, R. Impagliazzo, J. Krajicek, P. Pudlak, A. Razborov, J. Sgall. ``Proof complexity in algebraic systems and constant depth Frege systems with modular counting.'' To appear in Computational Complexity
S.R. Buss and T. Pitassi. ``Good degree bounds on Nullstellensatz refutations of the induction principle.'' To appear in Journal of Computer and System Sciences. Preliminary version appeared in Complexity '96, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, IEEE Press, 1996, pages 233-242
S.R. Buss and T. Pitassi. ``Resolution and the weak pigeonhole principle.'' To appear in Computer Science Logic '97 (CSL'97), Lecture Notes in Computer Science, Springer-Verlag
A. Carbone. A combinatorial theory of duplication and the structure of proofs. Submitted for publication, 1997
A. Carbone. Turning cycles into spirals. Annals of Pure and Applied Logic, to appear, 1997
A. Carbone and S. Semmes. Making Proofs without modus ponens: An introduction to the combinatorics and complexity of cut elimination. Bulletin of the American Mathematical Society, 1997, 34, pages 131-159
A. Carbone and S. Semmes. Propositional Proofs via Combinatorial Geometry and the Search for Symmetry. IHES preprint M/96/, to appear in Collegium Logicum - Annals of the Kurt Godel Society, 1998
G. Cherlin and B.J. Latka. A decision problem involving tournaments. DIMACS Technical Report 96-11, 1996
G. Cherlin and B.J. Latka. Forbidden subtournaments. Submitted to J. Comb. Th. (B)
A. Dawar, L. Hella, A. Seth. Ordering Finite Variable Types with Generalized Quantifiers, To appear in the Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, June, 1998
C. Daws, A. Olivero, S. Tripakis, S. Yovine. The tool KRONOS. Hybrid Systems III, Verification and Control, Lecture Notes in Computer Science 1066, Springer-Verlag, October 1995, pages 208-219
P.C. Eklof, B. Huisgen-Zimmermann, S. Shelah. Torsion modules, lattices and p-points. Bulletin of the London Mathematical Society, accepted
K. Etessami, M.Y. Vardi, T. Wilke. First-order with two variables and unary temporal logic. Proceedings of the 12th IEEE Symposium on Logic in Computer Science, June 1997, pages 228-235
K. Etessami and T. Wilke. An Until Hierarchy for Temporal Logic. Proceedings of the 11th IEEE Symposium on Logic in Computer Science, 1996, Journal version submitted to special issue of Information and Computation (LICS'96)
J. Feigenbaum, S. Kannan, M.Y. Vardi, and M. Vishwanathan. Complexity of Problems on Graphs Represented as OBDDs. Proceedings of the 15th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pages 216-222
E. Gradel, P.G. Kolaitis, M.Y. Vardi. On the Decision Problem for Two-Variable First-Order Logic. The Bulletin of Symbolic Logic, 3(1997), pages 53-69
M. Grohe. Equivalence in finite variable logics is complete for polynomial time. Proceedings of the 37th Annual Symposium on Foundations of Computer Science FOCS'96), October 1996, pages 264-273
R.H. Hardin, R.P. Kurshan, S.K. Shukla, M.Y. Vardi. A new heuristic for bad cycle detection using BDDs. Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'97), Lecture Notes in Computer Science 1254, Springer-Verlag, June 1997, pages 268-278
D. Harel, O. Kupferman, M.Y. Vardi. On the complexity of verifying concurrent transition systems. Proceedings of the 8th International Conference on Concurrency Theory (CONCUR'97), Lecture Notes in Computer Science 1243, Springer-Verlag, July 1997, pages 258-272
N. Immerman. Special Year on Logic and Algorithms Tutorial Notes: Descriptive Complexity, DIMACS Tech Report 97-55, 1997
N. Immerman and P.G. Kolaitis, eds. Descriptive Complexity and Finite Models, American Mathematical Society, 1997, 248 pages
N. Immerman, M.Y. Vardi. Model checking and transitive-closure logic. Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'97), Lecture Notes in Computer Science 1254, Springer-Verlag, June 1997, pages 291-302
R. Jin and S. Shelah. Compactness of Loeb Spaces. Journal of Symbolic Logic, accepted
B.M. Kapron. Feasibly continuous type-two functionals. To appear in computational complexity
P. Kolaitis. Special Year on Logic and Algorithms Tutorial Notes: Expressive Powers of Logics, DIMACS Tech Report 97-54, 1997
O. Kupferman, M.Y. Vardi. Module Checking. In Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'96), Lecture Notes in Computer Science 1102, Springer-Verlag, July 1996, pages 75-86 (invited to a special issue of Formal Methods in System Design)
O. Kupferman, M.Y. Vardi. Module Checking Revisited. Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'97), Lecture Notes in Computer Science 1254, Springer-Verlag, pages 36-47
O. Kupferman, M.Y. Vardi. Synthesis with incomplete information. Proceedings of the 2nd International Conference on Temporal Logic, July 1997, pages 91-106
O. Kupferman, M.Y. Vardi. Verification of fair transition systems. In Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'96), Lecture Notes in Computer Sciecne 1102, Springer-Verlag, July 1996, pages 372-382
O. Kupferman, M.Y. Vardi. Weal alternating automata are not that weak. Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, June 1997, pages 147-158
R. Kurshan and S. Shukla. Special Year on Logic and Algorithms Tutorial Notes: Complexity Issues in Automata-Theoretic Verification: The COSPAN Approach to Deal with These Issues, DIMACS Tech Report 97-57, 1997
B.J. Latka. A decidability result for quasi-orderings defined by obstructions. Submitted to Discrete Math
B.J. Latka. Session II. DIMACS Technical Report 97-54, Special Year on Logic and Algorithms Tutorial Notes: Expressive Power of Logics, E. Allender, ed., September 1997, pages 5-10
B.J. Latka. Well-quasi-ordered classes of tournaments. To appear in Proceedings of the 8th Quadrennial International Conference on Graph Theory, Combinatorics, Algorithms, and Applications
A. Lisitsa and V. Sazonov. Bounded Hyperset Theory and Web-like Data Bases. DIMACS Technical Report 97-21, Rutgers University, June 1997
A. Lisitsa and V. Sazonov. Delta-languages for sets and LOGSPACE computable graph transformers. Theoretical Computer Science (175) 1, 1997, pages 183-222
A. Lisitsa and V. Sazonov. On linear ordering of strongly extensional finitely-branching graphs and non-well-founded sets. DIMACS Technical Report 97-05, Rutgers University, February 1997
J.F. Lynch. Convergence Laws for Random Graphs, to appear in Proceedings of the ASL 95 Logic Colloquium, Lecture Notes in Mathematics, V. Harnik and J. Makowsky, eds., Springer-Verlag
J.F. Lynch. Pebble Games in Model Theory. Structures in Logic and Computer Science, Lecture Notes in Computer Science 1261, J. Mycielski, G. Rozenberg, A. Salomaa, eds., Springer-Verlag, 1997, pages 66-83
J.F. Lynch. Special Year on Logic and Algorithms tutorial notes: Random Finite Models, DIMACS Tech Report 97-56, 1997
L. Pacholski, P. Krysta. The STO problem is NP-complete. Journal of Symbolic Computation, to appear
L. Pacholski, W. Szwast, L. Tendera. Complexity of Two-Variable Logic with Counting. Proceedings of the 12th IEEE Symposium on Logic in Computer Science, Los Alamitos 1997, pages 318-327
D. Peled, T. Wilke, and P. Wolper. An algorithmic approach for checking closure properties of omega-regular languages. In Proc. CONCUR '96, volume 1119 of Lecture Notes in Computer Science, Springer-Verlag, Pisa, August 1996, pages 596-610
D. Peled, T. Wilke, and P. Wolper. An algorithmic approach for checking closure properties of temporal logic specifications and omega-regular languages. Theoretical Computer Science, 195(2):183--203, 1998
E. Rosen, S. Shelah, S. Weinstein. k-Universal finite graphs. Logic and Random Structures: DIMACS Workshop, November 5-7, 1995 R.B. Boppana and J.F. Lynch, eds, DIMACS series in discrete mathematics and theoretical computer science, v. 33, American Mathematical Society, 1997, pages 65-77
V. Sazonov and D. Sviridenko. Abstract deducibility and domain theory. DIMACS Technical Report 96-08, Rutgers University, May 1996
A. Seth. Implicit Definability vs. Weak Implicit Definability in Finite Model Theory, manuscript, 1996
A. Seth. A note on Ramified Version of McColm's Second Conjecture, manuscript, 1997 (to be revised)
A. Seth. Sharper Results on the Expressive Power of Generalized Quantifiers. Proceedings of the 17th Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 17), Lecture Notes in Computer Science (to appear), Springer-Verlag, December 1997
H. Schlingloff. Modelling Message Buffers with Binary Decision Diagrams. Proceedings of the 3rd International Conference on Relational Methods in Computer Science (RelMiCS'97), Hammamet, University of Tunis, Tunesia, 1997, pages 101-113
H. Schlingloff. Verification of Finite-State Systems with Temporal Logic Model Checking. South African Computer Journal, 1997
A. Seth. Sharper results on the expressive power of generalized quantifiers. In Proceedings of 17th FST & TCS conference, Springer LNCS 1346, pages 200-219, 1997
S. Shelah. Erdos and Renyi Conjecture. Journal of Combinatorial Theory. Ser. A, accepted
J.H. Spencer, K. St. John. Random Sparse Bit Strings at the Threshold of Adjacency, Proc. 15th Symposium on the Theoretical Aspects of Computer Science (STACS'98), Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pp. 94-104.
P.S. Thiagarajan and I. Walukiewicz. An expressively Complete Linear Time Temporal Logic. (LICS'97), 1997, pages 183-194
S. Tripakis and S. Yovine. Analysis of timed systems based on time-abstracting bisimulations. Proceedings of the 8th International Conference on Computer-Aided Verification (CAV'96), Lecture Notes in Computer Science 1102, Springer-Verlag, July 1996, pages 232-243
M.Y. Vardi. Why is modal logic so robustly decidable? In Descriptive Complexity and Finite Models, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 31, AMS, 1997, pages 149-184
External Evaluation Report
DIMACS home page
Contacting the Center
Last modified August 7, 1998