default search action
Johann A. Makowsky
Janos Makowsky
Person information
- affiliation: Technion - Israel Institute of Technology, Haifa, Israel
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [j65]Eldar Fischer, Johann A. Makowsky:
Extensions and Limits of the Specker-Blatter Theorem. J. Symb. Log. 89(3): 1284-1312 (2024) - [c72]Eldar Fischer, Johann A. Makowsky:
Extensions and Limits of the Specker-Blatter Theorem. CSL 2024: 26:1-26:20 - 2023
- [j64]Johann A. Makowsky, Vsevolod Rakita:
Almost unimodal and real-rooted graph polynomials. Eur. J. Comb. 108: 103637 (2023) - 2022
- [j63]Tomer Kotek, Johann A. Makowsky:
On the Tutte and Matching Polynomials for Complete Graphs. Fundam. Informaticae 186(1-4): 155-173 (2022) - 2021
- [c71]Johann A. Makowsky:
Some Thoughts on Computational Models: From Massive Human Computing to Abstract State Machines, and Beyond. Logic, Computation and Rigorous Methods 2021: 173-186 - 2020
- [c70]Johann A. Makowsky:
To Yuri at 80 and More than 40 Years of Friendship. Fields of Logic and Computation III 2020: 3-6 - [i10]Orli Herscovici, Johann A. Makowsky, Vsevolod Rakita:
Harary polynomials. CoRR abs/2003.06250 (2020)
2010 – 2019
- 2019
- [j62]Johann A. Makowsky, R. X. Zhang:
On P-unique hypergraphs. Australas. J Comb. 73: 456-465 (2019) - [j61]Johann A. Makowsky:
Can one design a geometry engine? - On the (un)decidability of certain affine Euclidean geometries. Ann. Math. Artif. Intell. 85(2-4): 259-291 (2019) - [j60]Johann A. Makowsky, Elena V. Ravve, Tomer Kotek:
A logician's view of graph polynomials. Ann. Pure Appl. Log. 170(9): 1030-1069 (2019) - [j59]Johann A. Makowsky, Vsevolod Rakita:
On Weakly Distinguishing Graph Polynomials. Discret. Math. Theor. Comput. Sci. 21(1) (2019) - [i9]Tomer Kotek, Johann A. Makowsky:
The exact complexity of the Tutte polynomial. CoRR abs/1910.08915 (2019) - 2018
- [j58]Andrew J. Goodall, Miki Hermann, Tomer Kotek, Johann A. Makowsky, Steven D. Noble:
On the complexity of generalized chromatic polynomials. Adv. Appl. Math. 94: 71-102 (2018) - [j57]Tomer Kotek, Johann A. Makowsky, Elena V. Ravve:
On sequences of polynomials arising from graph invariants. Eur. J. Comb. 67: 181-198 (2018) - [c69]Johann A. Makowsky:
The Undecidability of Orthogonal and Origami Geometries. WoLLIC 2018: 250-270 - 2017
- [j56]Johann A. Makowsky, Anna Zamansky:
Keeping logic in the trivium of computer science: a teaching perspective. Formal Methods Syst. Des. 51(2): 419-430 (2017) - [i8]Andrew J. Goodall, Miki Hermann, Tomer Kotek, Johann A. Makowsky, Steven D. Noble:
On the complexity of generalized chromatic polynomials. CoRR abs/1701.06639 (2017) - [i7]Johann A. Makowsky:
Can one design a geometry engine? On the (un)decidability of affine Euclidean geometries. CoRR abs/1712.07474 (2017) - 2016
- [c68]Nadia Labai, Johann A. Makowsky:
Hankel Matrices for Weighted Visibly Pushdown Automata. LATA 2016: 464-477 - [c67]Nadia Labai, Johann A. Makowsky:
On the Exact Learnability of Graph Parameters: The Case of Partition Functions. MFCS 2016: 63:1-63:13 - [c66]Johann A. Makowsky, Elena V. Ravve:
Semantic Equivalence of Graph Polynomials Definable in Second Order Logic. WoLLIC 2016: 279-296 - [i6]Nadia Labai, Johann A. Makowsky:
On the exact learnability of graph parameters: The case of partition functions. CoRR abs/1606.04056 (2016) - [i5]Joanna A. Ellis-Monaghan, Andrew J. Goodall, Johann A. Makowsky, Iain Moffatt:
Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241). Dagstuhl Reports 6(6): 26-48 (2016) - 2015
- [c65]Nadia Labai, Johann A. Makowsky:
Logics of Finite Hankel Rank. Fields of Logic and Computation II 2015: 237-252 - [c64]Johann A. Makowsky, Nadia Labai:
Hankel Matrices: From Words to Graphs (Extended Abstract). LATA 2015: 47-55 - [c63]Tomer Kotek, Johann A. Makowsky:
Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width. TTCS 2015: 135-146 - [i4]Tomer Kotek, Johann A. Makowsky:
Efficient computation of generalized Ising polynomials on graphs with fixed clique-width. CoRR abs/1505.06617 (2015) - [i3]Johann A. Makowsky:
Teaching Logic for Computer Science: Are We Teaching the Wrong Narrative? CoRR abs/1507.03672 (2015) - [i2]Nadia Labai, Johann A. Makowsky:
Hankel Matrices for Weighted Visibly Pushdown Automata. CoRR abs/1512.02430 (2015) - 2014
- [j55]Tomer Kotek, Johann A. Makowsky:
Connection Matrices and the Definability of Graph Parameters. Log. Methods Comput. Sci. 10(4) (2014) - [j54]Johann A. Makowsky, Elena V. Ravve, N. K. Blanchard:
On the location of roots of graph polynomials. Eur. J. Comb. 41: 1-19 (2014) - [j53]Tomer Kotek, Johann A. Makowsky:
Recurrence relations for graph polynomials on bi-iterative families of graphs. Eur. J. Comb. 41: 47-67 (2014) - [j52]Tomer Kotek, Johann A. Makowsky:
A representation theorem for (q-)holonomic sequences. J. Comput. Syst. Sci. 80(2): 363-374 (2014) - 2013
- [j51]Johann A. Makowsky, Elena V. Ravve:
On the Location of Roots of Graph Polynomials. Electron. Notes Discret. Math. 43: 201-206 (2013) - [c62]Nadia Labai, Johann A. Makowsky:
Weighted Automata and Monadic Second Order Logic. GandALF 2013: 122-135 - 2012
- [j50]Arnaud Durand, Neil D. Jones, Johann A. Makowsky, Malika More:
Fifty years of the spectrum problem: survey and new results. Bull. Symb. Log. 18(4): 505-553 (2012) - [j49]Tomer Kotek, Johann A. Makowsky:
A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths. Fundam. Informaticae 117(1-4): 199-213 (2012) - [j48]Sri Gopal Mohanty, Simone Rinaldi, Johann A. Makowsky:
Foreword. Fundam. Informaticae 117(1-4) (2012) - [j47]Benny Godlin, Emilia Katz, Johann A. Makowsky:
Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas. J. Log. Comput. 22(2): 237-265 (2012) - [c61]Johann A. Makowsky, Elena V. Ravve:
BCNF via Attribute Splitting. Conceptual Modelling and Its Theoretical Foundations 2012: 73-84 - [c60]Johann A. Makowsky:
Definability and Complexity of Graph Parameters (Invited Talk). CSL 2012: 14-15 - [c59]Tomer Kotek, Johann A. Makowsky:
Connection Matrices and the Definability of Graph Parameters. CSL 2012: 411-425 - [c58]Tomer Kotek, Johann A. Makowsky, Elena V. Ravve:
A Computational Framework for the Study of Partition Functions and Graph Polynomials. SYNASC 2012: 365-368 - 2011
- [j46]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) - [j45]Ilya Averbouch, Tomer Kotek, Johann A. Makowsky, Elena V. Ravve:
The Universal Edge Elimination Polynomial and the Dichromatic Polynomial. Electron. Notes Discret. Math. 38: 77-82 (2011) - [c57]Johann A. Makowsky:
Model Theory in Computer Science: My Own Recurrent Themes. CSL 2011: 553-567 - [e3]Martin Grohe, Johann A. Makowsky:
Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009. Contemporary Mathematics 558, American Mathematical Society 2011, ISBN 978-0-8218-4943-9 [contents] - 2010
- [j44]Ilya Averbouch, Benny Godlin, Johann A. Makowsky:
An extension of the bivariate chromatic polynomial. Eur. J. Comb. 31(1): 1-17 (2010) - [j43]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) - [c56]Tomer Kotek, Johann A. Makowsky:
Definability of Combinatorial Functions and Their Linear Recurrence Relations. Fields of Logic and Computation 2010: 444-462 - [c55]Johann A. Makowsky, Damian Niwinski:
The Ackermann Award 2010. CSL 2010: 544-546 - [c54]Johann A. Makowsky:
Application of Logic to Integer Sequences: A Survey. WoLLIC 2010: 34-41
2000 – 2009
- 2009
- [c53]Eldar Fischer, Tomer Kotek, Johann A. Makowsky:
Application of logic to combinatorial sequences and their recurrence relations. AMS-ASL Joint Special Session 2009: 1-42 - [c52]Tomer Kotek, Johann A. Makowsky, Boris Zilber:
On Counting Generalized Colorings. AMS-ASL Joint Special Session 2009: 207-242 - [c51]Johann A. Makowsky, Alexander A. Razborov:
The Ackermann Award 2009. CSL 2009: 561-565 - [c50]Johann A. Makowsky:
Connection Matrices for MSOL-Definable Structural Invariants. ICLA 2009: 51-64 - [c49]Ilya Averbouch, Johann A. Makowsky, Peter Tittmann:
A Graph Polynomial Arising from Community Structure (Extended Abstract). WG 2009: 33-43 - 2008
- [j42]Johann A. Makowsky:
From Hilbert's program to a logic tool box. Ann. Math. Artif. Intell. 53(1-4): 225-250 (2008) - [j41]Eldar Fischer, Johann A. Makowsky, Elena V. Ravve:
Counting truth assignments of formulas of bounded tree-width or clique-width. Discret. Appl. Math. 156(4): 511-529 (2008) - [j40]Ariel Cohen, Michael Kaminski, Johann A. Makowsky:
Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning. J. Log. Lang. Inf. 17(3): 285-306 (2008) - [j39]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) - [c48]Eldar Fischer, Johann A. Makowsky:
Linear Recurrence Relations for Graph Polynomials. Pillars of Computer Science 2008: 266-279 - [c47]Johann A. Makowsky:
Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants. CiE 2008: 403-406 - [c46]Tomer Kotek, Johann A. Makowsky, Boris Zilber:
On Counting Generalized Colorings. CSL 2008: 339-353 - [c45]Johann A. Makowsky, Damian Niwinski:
The Ackermann Award 2008. CSL 2008: 508-512 - [c44]Markus Bläser, Holger Dell, Johann A. Makowsky:
Complexity of the Bollobás-Riordan Polynomial. CSR 2008: 86-98 - [c43]Johann A. Makowsky:
From Hilbert's Program to a Logic Toolbox. ISAIM 2008 - [c42]Ilya Averbouch, Benny Godlin, Johann A. Makowsky:
A Most General Edge Elimination Polynomial. WG 2008: 31-42 - [c41]Benny Godlin, Tomer Kotek, Johann A. Makowsky:
Evaluations of Graph Polynomials. WG 2008: 183-194 - [i1]Benny Godlin, Emilia Katz, Johann A. Makowsky:
Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas. CoRR abs/0812.1364 (2008) - 2007
- [c40]Martin Grohe, Martin Hyland, Johann A. Makowsky, Damian Niwinski:
The Ackermann Award 2007. CSL 2007: 589-597 - [c39]Johann A. Makowsky:
From Hilbert's Program to a Logic Toolbox. LPAR 2007: 1 - 2006
- [c38]Johann A. Makowsky:
From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials. CiE 2006: 330-341 - [c37]Samson Abramsky, Erich Grädel, Johann A. Makowsky:
The Ackermann Award 2006. CSL 2006: 622-626 - [c36]Johann A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin:
Computing Graph Polynomials on Graphs of Bounded Clique-Width. WG 2006: 191-204 - 2005
- [j38]Johann A. Makowsky:
Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discret. Appl. Math. 145(2): 276-290 (2005) - [c35]Ariel Cohen, Michael Kaminski, Johann A. Makowsky:
Indistinguishability by Default. We Will Show Them! (1) 2005: 415-428 - [c34]Erich Grädel, Janos Makowsky, Alexander A. Razborov:
The Ackermann Award 2005. CSL 2005: 557-565 - [c33]Johann A. Makowsky:
Clemens Lautemann: 1951-2005 An Obituary. CSL 2005: 566-566 - 2004
- [j37]Martin Lotz, Johann A. Makowsky:
On the algebraic complexity of some families of coloured Tutte polynomials. Adv. Appl. Math. 32(1-2): 327-349 (2004) - [j36]Johann A. Makowsky:
Algorithmic uses of the Feferman-Vaught Theorem. Ann. Pure Appl. Log. 126(1-3): 159-213 (2004) - [j35]Eldar Fischer, Johann A. Makowsky:
On spectra of sentences of monadic second order logic with counting. J. Symb. Log. 69(3): 617-640 (2004) - 2003
- [j34]Johann A. Makowsky, Julian Mariño:
Farrell polynomials on graphs of bounded tree width. Adv. Appl. Math. 30(1-2): 160-176 (2003) - [j33]Johann A. Makowsky, Julian Mariño:
The parametrized complexity of knot polynomials. J. Comput. Syst. Sci. 67(4): 742-756 (2003) - [j32]Johann A. Makowsky, Julian Mariño:
Tree-width and the monadic quantifier hierarchy. Theor. Comput. Sci. 303(1): 157-170 (2003) - [c32]Eldar Fischer, Johann A. Makowsky:
The Specker-Blatter Theorem Revisited. COCOON 2003: 90-101 - [c31]Alexander Glikson, Johann A. Makowsky:
NCE Graph Grammars and Clique-Width. WG 2003: 237-248 - [e2]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. Lecture Notes in Computer Science 2803, Springer 2003, ISBN 3-540-40801-0 [contents] - 2002
- [j31]Bruno Courcelle, Johann A. Makowsky:
Fusion in Relational Structures and the Verification of Monadic Second-Order Properties. Math. Struct. Comput. Sci. 12(2): 203-235 (2002) - 2001
- [j30]Bruno Courcelle, Johann A. Makowsky, Udi Rotics:
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discret. Appl. Math. 108(1-2): 23-52 (2001) - [c30]Johann A. Makowsky:
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. SODA 2001: 487-495 - 2000
- [j29]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) - [c29]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
1990 – 1999
- 1999
- [j28]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
- [j27]Johann A. Makowsky, Y. B. Pnueli:
Erratum to "Arity and Alternation in Second-Order Logic". Ann. Pure Appl. Log. 92(2): 215 (1998) - [j26]Johann A. Makowsky, Elena V. Ravve:
Dependency Preserving Refinements and the Fundamental Problem of Database Design. Data Knowl. Eng. 24(3): 277-312 (1998) - [j25]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) - [c28]Johann A. Makowsky:
Invariant Definability and P/poly. CSL 1998: 142-158 - [c27]Bruno Courcelle, Johann A. Makowsky, Udi Rotics:
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. WG 1998: 1-16 - [e1]Johann A. Makowsky, Elena V. Ravve:
Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, Logic Colloquium 1995, Haifa, Israel, August 9-18, 1995. Lecture Notes in Logic 11, Springer 1998, ISBN 978-3-540-63994-7 [contents] - 1997
- [j24]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) - [j23]Jirí Adámek, Peter T. Johnstone, Johann A. Makowsky, Jirí Rosický:
Finitary Sketches. J. Symb. Log. 62(3): 699-707 (1997) - [c26]Johann A. Makowsky:
Invariant Definability (Extended Abstract). Kurt Gödel Colloquium 1997: 186-202 - [c25]Johann A. Makowsky, Elena V. Ravve:
The Fundamental Problem of Database Design. SOFSEM 1997: 53-69 - 1996
- [j22]Johann A. Makowsky, Y. B. Pnueli:
Arity and Alternation in Second-Order Logic. Ann. Pure Appl. Log. 78(1-3): 189-202 (1996) - [c24]Johann A. Makowsky, Elena V. Ravve:
Translation Schemes and the Fundamental Problem of Database Design. ER 1996: 5-26 - [c23]Michael Kaminski, Johann A. Makowsky, Michael L. Tiomkin:
Extensions for Open Default Theories via the Domain Closure Assumption. JELIA 1996: 373-387 - 1995
- [j21]Johann A. Makowsky, Abraham Sharell:
On Average Case Complexity of SAT for Symmetric Distribution. J. Log. Comput. 5(1): 71-92 (1995) - [c22]Johann A. Makowsky, Elena V. Ravve:
Incremental Model Checking for Decomposable Structures (Extended Abstract). MFCS 1995: 540-551 - 1994
- [c21]Johann A. Makowsky, Y. B. Pnueli:
Logics Capturing Relativized Complexity Classes Uniformly. LCC 1994: 463-479 - [c20]Johann A. Makowsky, Y. B. Pnueli:
Arity vs. Alternation in Second Order Logic. LFCS 1994: 240-252 - [c19]Johann A. Makowsky:
Capturing Complexity Classes with Lindström Quantifiers. MFCS 1994: 68-71 - 1993
- [j20]Johann A. Makowsky:
Book Review: Predicate Transformer Semantics. By Ernest G. Manes. (Cambridge University Press, 1992, 233pp. ISBN 0-521-42036-9. $39.95). SIGACT News 24(4): 36-38 (1993) - [c18]Johann A. Makowsky, Y. B. Pnueli:
Oracles and Quantifiers. CSL 1993: 189-222 - 1992
- [j19]Elias Dahlhaus, Johann A. Makowsky:
Query Languages for Hierarchic Databases. Inf. Comput. 101(1): 1-32 (1992) - [j18]Jacob P. Ukelson, Johann A. Makowsky:
Formal Interactive Menu Design. Interact. Comput. 4(1): 83-101 (1992) - [j17]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) - [c17]A. Calò, Johann A. Makowsky:
The Ehrenfeucht-Fraisse Games for Transitive Closure. LFCS 1992: 57-68 - 1991
- [j16]Michael L. Tiomkin, Johann A. Makowsky:
Decidability of Finite Probablistic Propositional Dynamic Logics. Inf. Comput. 94(2): 180-203 (1991) - [c16]Yaniv Bargury, Johann A. Makowsky:
The Expressive Power of Transitive Closue and 2-way Multihead Automata. CSL 1991: 1-14 - 1990
- [j15]Victor M. Markowitz, Johann A. Makowsky:
Identifying Extended Entity-Relationship Object Structures in Relational Schemas. IEEE Trans. Software Eng. 16(8): 777-790 (1990)
1980 – 1989
- 1989
- [j14]Johann A. Makowsky, Ildikó Sain:
Weak Second Order Characterizations of Various Program Verification Systems. Theor. Comput. Sci. 66(3): 299-321 (1989) - 1988
- [j13]