Janos Makowsky
List of publications from the DBLP Bibliography Server - FAQ
2009 | ||
---|---|---|
79 | EE | Johann A. Makowsky: Connection Matrices for MSOL-Definable Structural Invariants. ICLA 2009: 51-64 |
2008 | ||
78 | EE | Tomer Kotek, Johann A. Makowsky, Boris Zilber: On Counting Generalized Colorings. CSL 2008: 339-353 |
77 | EE | Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2008. CSL 2008: 508-512 |
76 | EE | Markus Bläser, Holger Dell, Johann A. Makowsky: Complexity of the Bollobás-Riordan Polynomial. CSR 2008: 86-98 |
75 | EE | Johann A. Makowsky: Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants. CiE 2008: 403-406 |
74 | EE | Eldar Fischer, Johann A. Makowsky: Linear Recurrence Relations for Graph Polynomials. Pillars of Computer Science 2008: 266-279 |
73 | EE | Benny Godlin, Tomer Kotek, Johann A. Makowsky: Evaluations of Graph Polynomials. WG 2008: 183-194 |
72 | EE | Ilya Averbouch, Benny Godlin, Johann A. Makowsky: A Most General Edge Elimination Polynomial. WG 2008: 31-42 |
71 | EE | Benny Godlin, Emilia Katz, Johann A. Makowsky: Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas CoRR abs/0812.1364: (2008) |
70 | EE | 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) |
69 | EE | 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) |
2007 | ||
68 | EE | Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski: The Ackermann Award 2007. CSL 2007: 589-597 |
67 | EE | Johann A. Makowsky: From Hilbert's Program to a Logic Toolbox. LPAR 2007: 1 |
2006 | ||
66 | EE | Samson Abramsky, Erich Grädel, Johann A. Makowsky: The Ackermann Award 2006. CSL 2006: 622-626 |
65 | EE | Johann A. Makowsky: From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials. CiE 2006: 330-341 |
64 | EE | Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin: Computing Graph Polynomials on Graphs of Bounded Clique-Width. WG 2006: 191-204 |
2005 | ||
63 | EE | Erich Grädel, Janos Makowsky, Alexander A. Razborov: The Ackermann Award 2005. CSL 2005: 557-565 |
62 | EE | Johann A. Makowsky: Clemens Lautemann: 1951-2005 An Obituary. CSL 2005: 566-566 |
61 | Ariel Cohen, Michael Kaminski, Johann A. Makowsky: Indistinguishability by Default. We Will Show Them! (1) 2005: 415-428 | |
60 | EE | Johann A. Makowsky: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Applied Mathematics 145(2): 276-290 (2005) |
2004 | ||
59 | EE | Johann A. Makowsky: Algorithmic uses of the Feferman-Vaught Theorem. Ann. Pure Appl. Logic 126(1-3): 159-213 (2004) |
2003 | ||
58 | Matthias Baaz, Johann A. Makowsky: 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 Springer 2003 | |
57 | EE | Eldar Fischer, Johann A. Makowsky: The Specker-Blatter Theorem Revisited. COCOON 2003: 90-101 |
56 | EE | Alexander Glikson, Johann A. Makowsky: NCE Graph Grammars and Clique-Width. WG 2003: 237-248 |
55 | EE | Johann A. Makowsky, Julian Mariño: The parametrized complexity of knot polynomials. J. Comput. Syst. Sci. 67(4): 742-756 (2003) |
54 | EE | Johann A. Makowsky, Julian Mariño: Tree-width and the monadic quantifier hierarchy. Theor. Comput. Sci. 1(303): 157-170 (2003) |
2002 | ||
53 | 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) | |
2001 | ||
52 | EE | Johann A. Makowsky: Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. SODA 2001: 487-495 |
51 | 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) | |
2000 | ||
50 | EE | 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 |
49 | EE | 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) |
1999 | ||
48 | Johann A. Makowsky, Udi Rotics: On the Clique-Width of Graphs with Few P4's. Int. J. Found. Comput. Sci. 10(3): 329-348 (1999) | |
1998 | ||
47 | Johann A. Makowsky: Invariant Definability and P/poly. CSL 1998: 142-158 | |
46 | Bruno Courcelle, Johann A. Makowsky, Udi Rotics: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. WG 1998: 1-16 | |
45 | Johann A. Makowsky, Y. B. Pnueli: Erratum to ``Arity and Alternation in Second-Order Logic. Ann. Pure Appl. Logic 92(2): 215 (1998) | |
44 | EE | Johann A. Makowsky, Elena V. Ravve: Dependency Preserving Refinements and the Fundamental Problem of Database Design. Data Knowl. Eng. 24(3): 277-312 (1998) |
43 | 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) | |
1997 | ||
42 | Johann A. Makowsky: Invariant Definability (Extended Abstract). Kurt Gödel Colloquium 1997: 186-202 | |
41 | Johann A. Makowsky, Elena V. Ravve: The Fundamental Problem of Database Design. SOFSEM 1997: 53-69 | |
40 | 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) | |
39 | Jirí Adámek, Peter T. Johnstone, Johann A. Makowsky, Jirí Rosický: Finitary Sketches. J. Symb. Log. 62(3): 699-707 (1997) | |
1996 | ||
38 | EE | Johann A. Makowsky, Elena V. Ravve: Translation Schemes and the Fundamental Problem of Database Design. ER 1996: 5-26 |
37 | Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin: Extensions for Open Default Theories via the Domain Closure Assumption. JELIA 1996: 373-387 | |
36 | Johann A. Makowsky, Y. B. Pnueli: Arity and Alternation in Second-Order Logic. Ann. Pure Appl. Logic 78(1-3): 189-202 (1996) | |
1995 | ||
35 | Johann A. Makowsky, Elena V. Ravve: Incremental Model Checking for Decomposable Structures (Extended Abstract). MFCS 1995: 540-551 | |
34 | Johann A. Makowsky, Abraham Sharell: On Average Case Complexity of SAT for Symmetric Distribution. J. Log. Comput. 5(1): 71-92 (1995) | |
1994 | ||
33 | Johann A. Makowsky, Y. B. Pnueli: Logics Capturing Relativized Complexity Classes Uniformly. LCC 1994: 463-479 | |
32 | Johann A. Makowsky, Y. B. Pnueli: Arity vs. Alternation in Second Order Logic. LFCS 1994: 240-252 | |
31 | Johann A. Makowsky: Capturing Complexity Classes with Lindström Quantifiers. MFCS 1994: 68-71 | |
1993 | ||
30 | Johann A. Makowsky, Y. B. Pnueli: Oracles and Quantifiers. CSL 1993: 189-222 | |
1992 | ||
29 | A. Calò, Johann A. Makowsky: The Ehrenfeucht-Fraisse Games for Transitive Closure. LFCS 1992: 57-68 | |
28 | Elias Dahlhaus, Johann A. Makowsky: Query Languages for Hierarchic Databases Inf. Comput. 101(1): 1-32 (1992) | |
27 | Jacob P. Ukelson, Johann A. Makowsky: Formal Interactive Menu Design. Interacting with Computers 4(1): 83-101 (1992) | |
26 | 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) | |
1991 | ||
25 | Yaniv Bargury, Johann A. Makowsky: The Expressive Power of Transitive Closue and 2-way Multihead Automata. CSL 1991: 1-14 | |
24 | Michael L. Tiomkin, Johann A. Makowsky: Decidability of Finite Probablistic Propositional Dynamic Logics Inf. Comput. 94(2): 180-203 (1991) | |
1990 | ||
23 | EE | Victor M. Markowitz, Johann A. Makowsky: Identifying Extended Entity-Relationship Object Structures in Relational Schemas. IEEE Trans. Software Eng. 16(8): 777-790 (1990) |
1989 | ||
22 | Johann A. Makowsky, Ildikó Sain: Weak Second Order Characterizations of Various Program Verification Systems. Theor. Comput. Sci. 66(3): 299-321 (1989) | |
1988 | ||
21 | EE | Victor M. Markowitz, Johann A. Makowsky: Incremental Restructuring of Relational Schemas. ICDE 1988: 276-284 |
1987 | ||
20 | EE | Victor M. Markowitz, Johann A. Makowsky: Incremental Reorganization of Relational Databases. VLDB 1987: 127-135 |
19 | 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) | |
18 | Alon Itai, Johann A. Makowsky: Unification as a Complexity Measure for Logic Programming. J. Log. Program. 4(2): 105-117 (1987) | |
1986 | ||
17 | Elias Dahlhaus, Johann A. Makowsky: Computable Directory Queries. CAAP 1986: 254-265 | |
16 | Elias Dahlhaus, Johann A. Makowsky: The Choice of Programming Primitives for SETL-Like Programming Languages. ESOP 1986: 160-172 | |
15 | EE | Johann A. Makowsky, Victor M. Markowitz, Nimrod Rotics: Entity-Relationship Consistency for Relational Schemas. ICDT 1986: 306-322 |
14 | 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 | |
13 | Johann A. Makowsky, Moshe Y. Vardi: On the Expressive Power of Data Dependencies. Acta Inf. 23(3): 231-244 (1986) | |
1985 | ||
12 | Johann A. Makowsky: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract). TAPSOFT, Vol.1 1985: 374-387 | |
11 | 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) | |
10 | Johann A. Makowsky: Vopenka's Principle and Compact Logics. J. Symb. Log. 50(1): 42-48 (1985) | |
9 | Michael L. Tiomkin, Johann A. Makowsky: Propositional Dynamic Logic with Local Assignments. Theor. Comput. Sci. 36: 71-87 (1985) | |
1984 | ||
8 | Bernd Mahr, Johann A. Makowsky: Characterizing Specification Languages which Admit Initial Semantics. Theor. Comput. Sci. 31: 49-59 (1984) | |
1983 | ||
7 | Bernd Mahr, Johann A. Makowsky: Characterizing Specification Languages Which Admit Initial Semantics. CAAP 1983: 300-316 | |
6 | Johann A. Makowsky, Bernd Mahr: An axiomatic approach to semantics of specification languages. Theoretical Computer Science 1983: 211-219 | |
1981 | ||
5 | Johann A. Makowsky: Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. ICALP 1981: 551 | |
4 | Johann A. Makowsky: Characterizing Data Base Dependencies. ICALP 1981: 86-97 | |
3 | Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem STOC 1981: 342-354 | |
1980 | ||
2 | Johann A. Makowsky: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory. ICALP 1980: 409-421 | |
1 | Ashok K. Chandra, Harry R. Lewis, Johann A. Makowsky: Embedded Implicational Dependencies and their Inference Problem. XP1 Workshop on Database Theory 1980 |