Prof. Johann Makowsky

Prof. Johann Makowsky

Contact information
Homepage:
http://www.cs.technion.ac.il/~janos/
Email:
janos[at]cs.technion.ac.il
Office:
628
Phone:
4358
Research interests
Logic and Complexity; Complexity over the Reals; Algebraic Combinatorics.
Selected publications

MAKOWSKY, J.A., and SHELAH, S., "Positive results in abstract model theory: A theory of compact logics", Annals of Pure and Applied Logic, Vol. 25, No. 3, pp. 263-300, 1983.

MAKOWSKY, J.A., "Compactness, embeddings and definability", Model Theoretic Logics, J. Barwise and S. Feferman (eds), Chap.18, pp. 645-716, Springer, 1985.

MAKOWSKY, J.A., "Vopenka's principle and compact logics", Journal of Symbolic Logic, Vol. 50, No.1, pp. 42-48, 1985.

ADAMEK, J., JOHNSTONE, P.T., MAKOWSKY, J.A., and ROSICKY, J., "Finitary sketches", Journal of Symbolic Logic, Vol. 62, No. 3, pp. 699-707, 1997.

MAKOWSKY, J.A., and RAVVE, E.V., "Dependency preserving refinements and the fundamental problem of database design", to appear in Data and Knowledge Engineering, Vol. 24, No. 3, pp. 277-312, 1998.

MAKOWSKY, J.A., and SHARELL, A., "On the average case complexity of SAT for symmetric distributions", Logic and Computation, Vol. 5, No. 1, pp. 71-92, 1995.

VENKATESAN, G., ROTICS, U., MADANLAL, M.S., MAKOWSKY, J.A., and PANDU RANGAN, C., "Restrictions of minimum spanner problems", Information and Computation, 136, pp. 143-164, 1997.

MAKOWSKY, J.A., and PNUELI, Y.B., "Arity vs. alternation in second order logic", Annals of Pure and Applied Logic, Vol. 78, No. 1-3, pp. 189-202, 1996.

KAMINSKI, M., MAKOWSKY, J.A., and TIOMKIN, M., "Extensions for open default theories via the domain closure assumption”, Logic and Computation, Vol. 8.2, pp. 169-187, 1998.

COURCELLE, B., MAKOWSKY, J.A. and ROTICS, U., "Linear time solvable optimization problems on graphs of bounded clique width", Theory of Computing Systems, Vol. 33-2, pp. 125-150, 1999.

MAKOWSKY, J.A., "Invariant Definability and P/poly", accepted for publication in the Poceedings of CSL'98, LNCS, Vol. 1584, pp. 142-158, 1999.

COURCELLE, B., MAKOWSKY, J.A., and ROTICS, U., "On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic", Discrete Applied Mathematics, Vol. 108, No. 1-2, pp. 23-52, 2001.

MAKOWSKY, J.A., "Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width", Proceedings of SODA'01, pp. 487-495, 2001.