Johann A. Makowsky

Tomer Kotek, Johann A. Makowsky: A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths. Fundam. Inform. 117(1-4): 199-213 (2012)

Sri Gopal Mohanty, Simone Rinaldi, Johann A. Makowsky: Foreword. Fundam. Inform. 117(1-4) (2012)

Benny Godlin, Emilia Katz, Johann A. Makowsky: Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas. J. Log. Comput. 22(2): 237-265 (2012)

Johann A. Makowsky, Elena V. Ravve: BCNF via Attribute Splitting. Conceptual Modelling and Its Theoretical Foundations 2012: 73-84

Johann A. Makowsky: Definability and Complexity of Graph Parameters (Invited Talk). CSL 2012: 14-15

Tomer Kotek, Johann A. Makowsky: Connection Matrices and the Definability of Graph Parameters. CSL 2012: 411-425

Tomer Kotek, Johann A. Makowsky, Elena V. Ravve: A Computational Framework for the Study of Partition Functions and Graph Polynomials. SYNASC 2012: 365-368

Peter Tittmann, Ilya Averbouch, Johann A. Makowsky: The enumeration of vertex induced subgraphs with respect to the number of components. Eur. J. Comb. 32(7): 954-974 (2011)

Ilya Averbouch, Tomer Kotek, Johann A. Makowsky, Elena V. Ravve: The Universal Edge Elimination Polynomial and the Dichromatic Polynomial. Electronic Notes in Discrete Mathematics 38: 77-82 (2011)

Johann A. Makowsky: Model Theory in Computer Science: My Own Recurrent Themes. CSL 2011: 553-567

Ilya Averbouch, Benny Godlin, Johann A. Makowsky: An extension of the bivariate chromatic polynomial. Eur. J. Comb. 31(1): 1-17 (2010)

Markus Bläser, Holger Dell, Johann A. Makowsky: Complexity of the Bollobás-Riordan Polynomial. Exceptional Points and Uniform Reductions. Theory Comput. Syst. 46(4): 690-706 (2010)

Tomer Kotek, Johann A. Makowsky: Definability of Combinatorial Functions and Their Linear Recurrence Relations. Fields of Logic and Computation 2010: 444-462

Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2010. CSL 2010: 544-546

Johann A. Makowsky: Application of Logic to Integer Sequences: A Survey. WoLLIC 2010: 34-41

Johann A. Makowsky, Alexander A. Razborov: The Ackermann Award 2009. CSL 2009: 561-565

Johann A. Makowsky: Connection Matrices for MSOL-Definable Structural Invariants. ICLA 2009: 51-64

Ilya Averbouch, Johann A. Makowsky, Peter Tittmann: A Graph Polynomial Arising from Community Structure (Extended Abstract). WG 2009: 33-43

Johann A. Makowsky: From Hilbert's program to a logic tool box. Ann. Math. Artif. Intell. 53(1-4): 225-250 (2008)

Eldar Fischer, Johann A. Makowsky, Elena V. Ravve: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics 156(4): 511-529 (2008)

Ariel Cohen, Michael Kaminski, Johann A. Makowsky: Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning. Journal of Logic, Language and Information 17(3): 285-306 (2008)

Johann A. Makowsky: From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials. Theory Comput. Syst. 43(3-4): 542-562 (2008)

Eldar Fischer, Johann A. Makowsky: Linear Recurrence Relations for Graph Polynomials. Pillars of Computer Science 2008: 266-279

Johann A. Makowsky: Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants. CiE 2008: 403-406

Tomer Kotek, Johann A. Makowsky, Boris Zilber: On Counting Generalized Colorings. CSL 2008: 339-353

Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2008. CSL 2008: 508-512

Markus Bläser, Holger Dell, Johann A. Makowsky: Complexity of the Bollobás-Riordan Polynomial. CSR 2008: 86-98

Johann A. Makowsky: From Hilbert's Program to a Logic Toolbox. ISAIM 2008

Ilya Averbouch, Benny Godlin, Johann A. Makowsky: A Most General Edge Elimination Polynomial. WG 2008: 31-42

Benny Godlin, Tomer Kotek, Johann A. Makowsky: Evaluations of Graph Polynomials. WG 2008: 183-194

Benny Godlin, Emilia Katz, Johann A. Makowsky: Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas. CoRR abs/0812.1364 (2008)

Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2007. CSL 2007: 589-597

Johann A. Makowsky: From Hilbert's Program to a Logic Toolbox. LPAR 2007: 1

Johann A. Makowsky: From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials. CiE 2006: 330-341

Samson Abramsky, Erich Grädel, Johann A. Makowsky: The Ackermann Award 2006. CSL 2006: 622-626

Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin: Computing Graph Polynomials on Graphs of Bounded Clique-Width. WG 2006: 191-204

Johann A. Makowsky: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Applied Mathematics 145(2): 276-290 (2005)

Ariel Cohen, Michael Kaminski, Johann A. Makowsky: Indistinguishability by Default. We Will Show Them! (1) 2005: 415-428

Erich Grädel, Janos Makowsky, Alexander A. Razborov: The Ackermann Award 2005. CSL 2005: 557-565

Johann A. Makowsky: Clemens Lautemann: 1951-2005 An Obituary. CSL 2005: 566-566

Johann A. Makowsky: Algorithmic uses of the Feferman-Vaught Theorem. Ann. Pure Appl. Logic 126(1-3): 159-213 (2004)

Eldar Fischer, Johann A. Makowsky: On spectra of sentences of monadic second order logic with counting. J. Symb. Log. 69(3): 617-640 (2004)

Johann A. Makowsky, Julian Mariño: The parametrized complexity of knot polynomials. J. Comput. Syst. Sci. 67(4): 742-756 (2003)

Johann A. Makowsky, Julian Mariño: Tree-width and the monadic quantifier hierarchy. Theor. Comput. Sci. 1(303): 157-170 (2003)

Eldar Fischer, Johann A. Makowsky: The Specker-Blatter Theorem Revisited. COCOON 2003: 90-101

Alexander Glikson, Johann A. Makowsky: NCE Graph Grammars and Clique-Width. WG 2003: 237-248

Matthias Baaz, Johann A. Makowsky (Eds.): Computer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings. Lecture Notes in Computer Science 2803, Springer 2003, isbn 3-540-40801-0

Bruno Courcelle, Johann A. Makowsky: Fusion in Relational Structures and the Verification of Monadic Second-Order Properties. Mathematical Structures in Computer Science 12(2): 203-235 (2002)

Bruno Courcelle, Johann A. Makowsky, Udi Rotics: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108(1-2): 23-52 (2001)

Johann A. Makowsky: Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. SODA 2001: 487-495

Bruno Courcelle, Johann A. Makowsky, Udi Rotics: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width. Theory Comput. Syst. 33(2): 125-150 (2000)

Johann A. Makowsky, Klaus Meer: On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale. CSL 2000: 399-410

Johann A. Makowsky, Udi Rotics: On the Clique-Width of Graphs with Few P₄'s. Int. J. Found. Comput. Sci. 10(3): 329-348 (1999)

Johann A. Makowsky, Y. B. Pnueli: Erratum to ``Arity and Alternation in Second-Order Logic. Ann. Pure Appl. Logic 92(2): 215 (1998)

Johann A. Makowsky, Elena V. Ravve: Dependency Preserving Refinements and the Fundamental Problem of Database Design. Data Knowl. Eng. 24(3): 277-312 (1998)

Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin: Extensions for Open Default Theories via the Domain Closure Assumption. J. Log. Comput. 8(2): 169-187 (1998)

Johann A. Makowsky: Invariant Definability and P/poly. CSL 1998: 142-158

Bruno Courcelle, Johann A. Makowsky, Udi Rotics: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. WG 1998: 1-16

G. Venkatesan, Udi Rotics, M. S. Madanlal, Johann A. Makowsky, C. Pandu Rangan: Restrictions of Minimum Spanner Problems. Inf. Comput. 136(2): 143-164 (1997)

Jirí Adámek, Peter T. Johnstone, Johann A. Makowsky, Jirí Rosický: Finitary Sketches. J. Symb. Log. 62(3): 699-707 (1997)

Johann A. Makowsky: Invariant Definability (Extended Abstract). Kurt Gödel Colloquium 1997: 186-202

Johann A. Makowsky, Elena V. Ravve: The Fundamental Problem of Database Design. SOFSEM 1997: 53-69

Johann A. Makowsky, Y. B. Pnueli: Arity and Alternation in Second-Order Logic. Ann. Pure Appl. Logic 78(1-3): 189-202 (1996)

Johann A. Makowsky, Elena V. Ravve: Translation Schemes and the Fundamental Problem of Database Design. ER 1996: 5-26

Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin: Extensions for Open Default Theories via the Domain Closure Assumption. JELIA 1996: 373-387

Johann A. Makowsky, Abraham Sharell: On Average Case Complexity of SAT for Symmetric Distribution. J. Log. Comput. 5(1): 71-92 (1995)

Johann A. Makowsky, Elena V. Ravve: Incremental Model Checking for Decomposable Structures (Extended Abstract). MFCS 1995: 540-551

Johann A. Makowsky, Y. B. Pnueli: Logics Capturing Relativized Complexity Classes Uniformly. LCC 1994: 463-479

Johann A. Makowsky, Y. B. Pnueli: Arity vs. Alternation in Second Order Logic. LFCS 1994: 240-252

Johann A. Makowsky: Capturing Complexity Classes with Lindström Quantifiers. MFCS 1994: 68-71

Johann A. Makowsky, Y. B. Pnueli: Oracles and Quantifiers. CSL 1993: 189-222

Elias Dahlhaus, Johann A. Makowsky: Query Languages for Hierarchic Databases. Inf. Comput. 101(1): 1-32 (1992)

Jacob P. Ukelson, Johann A. Makowsky: Formal Interactive Menu Design. Interacting with Computers 4(1): 83-101 (1992)

Johann A. Makowsky, J.-C. Gregoire, Shmuel Sagiv: The Expressive Power of Side Effects in Prolog. J. Log. Program. 12(1&2): 179-188 (1992)

A. Calò, Johann A. Makowsky: The Ehrenfeucht-Fraisse Games for Transitive Closure. LFCS 1992: 57-68

Michael L. Tiomkin, Johann A. Makowsky: Decidability of Finite Probablistic Propositional Dynamic Logics. Inf. Comput. 94(2): 180-203 (1991)

Yaniv Bargury, Johann A. Makowsky: The Expressive Power of Transitive Closue and 2-way Multihead Automata. CSL 1991: 1-14

Victor M. Markowitz, Johann A. Makowsky: Identifying Extended Entity-Relationship Object Structures in Relational Schemas. IEEE Trans. Software Eng. 16(8): 777-790 (1990)

Johann A. Makowsky, Ildikó Sain: Weak Second Order Characterizations of Various Program Verification Systems. Theor. Comput. Sci. 66(3): 299-321 (1989)

Victor M. Markowitz, Johann A. Makowsky: Incremental Restructuring of Relational Schemas. ICDE 1988: 276-284

Johann A. Makowsky: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples. J. Comput. Syst. Sci. 34(2/3): 266-292 (1987)

Alon Itai, Johann A. Makowsky: Unification as a Complexity Measure for Logic Programming. J. Log. Program. 4(2): 105-117 (1987)

Victor M. Markowitz, Johann A. Makowsky: Incremental Reorganization of Relational Databases. VLDB 1987: 127-135

Johann A. Makowsky, Moshe Y. Vardi: On the Expressive Power of Data Dependencies. Acta Inf. 23(3): 231-244 (1986)

Elias Dahlhaus, Johann A. Makowsky: Computable Directory Queries. CAAP 1986: 254-265

Elias Dahlhaus, Johann A. Makowsky: The Choice of Programming Primitives for SETL-Like Programming Languages. ESOP 1986: 160-172

Johann A. Makowsky, Victor M. Markowitz, Nimrod Rotics: Entity-Relationship Consistency for Relational Schemas. ICDT 1986: 306-322

Johann A. Makowsky, Ildikó Sain: On the Equivalence of Weak Second Order and Nonstandard Time Semantics For Various Program Verification Systems. LICS 1986: 293-300

Orna Grumberg, Nissim Francez, Johann A. Makowsky, Willem P. de Roever: A Proof Rule for Fair Termination of Guarded Commands. Information and Control 66(1/2): 83-102 (1985)

Johann A. Makowsky: Vopenka's Principle and Compact Logics. J. Symb. Log. 50(1): 42-48 (1985)

Michael L. Tiomkin, Johann A. Makowsky: Propositional Dynamic Logic with Local Assignments. Theor. Comput. Sci. 36: 71-87 (1985)

Johann A. Makowsky: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract). TAPSOFT, Vol.1 1985: 374-387

Bernd Mahr, Johann A. Makowsky: Characterizing Specification Languages which Admit Initial Semantics. Theor. Comput. Sci. 31: 49-59 (1984)

Bernd Mahr, Johann A. Makowsky: Characterizing Specification Languages Which Admit Initial Semantics. CAAP 1983: 300-316

Johann A. Makowsky, Bernd Mahr: An axiomatic approach to semantics of specification languages. Theoretical Computer Science 1983: 211-219

Johann A. Makowsky: Characterizing Data Base Dependencies. ICALP 1981: 86-97

Johann A. Makowsky: Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. ICALP 1981: 551

Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. STOC 1981: 342-354

Johann A. Makowsky: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. ICALP 1980: 409-421

Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. XP1 Workshop on Database Theory 1980