Johann Makowsky

Q: What Schools Are Affiliated With Johann Makowsky

Johann Makowsky is affiliated with the following schools: ETH Zurich, University of Zurich

Johann Makowsky's AcademicInfluence.com Rankings

Johann Makowsky

Mathematics

#5224

World Rank

#7369

Historical Rank

Measure Theory

#2831

World Rank

#3369

Historical Rank

mathematics Degrees

Download Badge

Mathematics

Johann Makowsky's Degrees

PhD Mathematics University of Zurich

Why Is Johann Makowsky Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Johann A. Makowsky is a Hungarian-born naturalised Swiss mathematician who works in mathematical logic and the logical foundations of computer science and combinatorics. He studied at ETH Zurich from 1967–73. He was a student in Zürich of Ernst Specker and Hans Läuchli in mathematical logic, , of Beno Eckmann and Volker Strassen , and in Warsaw of Andrzej Mostowski and Witek Marek, where he spent 1972 as an exchange student. Makowsky held visiting positions at the Banach Center in Warsaw , Stanford University , Simon Fraser University , University of Florence , MIT , Lausanne University and ETH Zurich . He held regular positions at the Free University of Berlin and the Technion – Israel Institute of Technology where he was a full professor.

(See a Problem?)

Johann Makowsky's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width (2000) (682)
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width (1998) (336)
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (2001) (213)
Algorithmic uses of the Feferman-Vaught Theorem (2004) (208)
Identifying Extended Entity-Relationship Object Structures in Relational Schemas (1990) (182)
Embedded implicational dependencies and their inference problem (1981) (124)
Counting truth assignments of formulas of bounded tree-width or clique-width (2008) (104)
On the Clique-Width of Graphs with Few P4's (1999) (87)
Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (1987) (83)
Unification as a Complexity Measure for Logic Programming (1987) (80)
A Proof Rule for Fair Termination of Guarded Commands (1985) (75)
Model Theoretic Methods in Finite Combinatorics (2011) (71)
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width (2001) (67)
δ-Logics and generalized quantifiers (1976) (67)
Characterizing Specification Languages which Admit Initial Semantics (1983) (58)
Computing Graph Polynomials on Graphs of Bounded Clique-Width (2006) (53)
Restrictions of Minimum Spanner Problems (1997) (51)
The quantum FFT can be classically simulated (2006) (48)
From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials (2008) (47)
An extension of the bivariate chromatic polynomial (2010) (45)
Fusion in relational structures and the verification of monadic second-order properties (2002) (39)
The enumeration of vertex induced subgraphs with respect to the number of components (2008) (35)
Model theory and computer science: an appetizer (1993) (32)
Arity and Alternation in Second-Order Logic (1996) (32)
On some conjectures connected with complete sentences (1974) (28)
The theorems of Beth and Craig in abstract model theory. I. The abstract setting (1979) (28)
Entity-Relationship Consistency for Relational Schemas (1986) (27)
A Most General Edge Elimination Polynomial (2008) (27)
Computable Quantifiers and Logics over Finite Structures (1995) (25)
Evaluations of Graph Polynomials (2008) (25)
On the location of roots of graph polynomials (2013) (25)
Computable Directory Queries (1986) (25)
On Counting Generalized Colorings (2008) (25)
On spectra of sentences of monadic second order logic with counting (2004) (24)
Farrell polynomials on graphs of bounded tree width (2003) (23)
Fifty years of the spectrum problem: survey and new results (2009) (23)
On the algebraic complexity of some families of coloured Tutte polynomials (2004) (23)
The parametrized complexity of knot polynomials (2003) (23)
Query Languages for Hierarchic Databases (1992) (23)
Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract) (1985) (22)
Tree-width and the monadic quantifier hierarchy (2003) (22)
Positive results in abstract model theory: a theory of compact logics (1983) (21)
Connection Matrices and the Definability of Graph Parameters (2013) (21)
Oracles and Quantifiers (1993) (21)
Some model theory for monotone quantifiers (1977) (20)
Propositional Dynamic Logic with Local Assignments (1985) (20)
Arity vs. Alternation in Second Order Logic (1994) (19)
The theorems of beth and Craig in abstract model theory II. Compact logics (1981) (19)
Dependency Preserving Refinements and the Fundamental Problem of Database Design (1998) (19)
NCE Graph Grammars and Clique-Width (2003) (18)
The Choice of Programming Primitives for SETL-Like Programming Languages (1986) (18)
POLYNOMIAL INVARIANTS OF GRAPHS AND TOTALLY CATEGORICAL THEORIES (2006) (17)
From a Zoo to a Zoology: Descriptive Complexity for Graph Polynomials (2006) (17)
Incremental Reorganization of Relational Databases (1987) (17)
Incremental Model Checking for Decomposable Structures (Extended Abstract) (1995) (17)
Characterizing Data Base Dependencies (1981) (16)
Extensions for Open Default Theories via the Domain Closure Assumption (1996) (16)
The Ehrenfeucht-Fraisse Games for Transitive Closure (1992) (16)
The Expressive Power of Transitive Closue and 2-way Multihead Automata (1991) (16)
A Computational Framework for the Study of Partition Functions and Graph Polynomials (2012) (15)
On the Equivalence of Weak Second Order and Nonstandard Time Semantics For Various Program Verification Systems (1986) (13)
Linear Recurrence Relations for Graph Polynomials (2008) (13)
The Specker-Blatter Theorem Revisited (2003) (12)
Application of logic to combinatorial sequences and their recurrence relations (2009) (12)
Model Theoretic Issues in Theoretical Computer Science, Part I: Relational Data Bases and Abstract Data Types (1984) (12)
Weak Second Order Characterizations of Various Program Verification Systems (1989) (11)
Weighted Automata and Monadic Second Order Logic (2013) (11)
Topological model theory with an interior operator: Consistency properties and back — and forth arguments (1981) (10)
On the expressive power of data dependencies (1986) (10)
Translation Schemes and the Fundamental Problem of Database Design (1996) (10)
Completeness Theorems For Modal Model Theory With the Montague-Chang Semantics I (1977) (10)
On the Complexity of Combinatorial and Metafinite Generating Functions of Graph Properties in the Computational Model of Blum, Shub and Smale (2000) (10)
Logics Capturing Relativized Complexity Classes Uniformly (1994) (10)
Recurrence relations for graph polynomials on bi-iterative families of graphs (2013) (9)
An axiomatic approach to semantics of specification languages (1983) (9)
Vopěnka's principle and compact logics (1985) (9)
From Hilbert’s program to a logic tool box (2008) (9)
Definability of Combinatorial Functions and Their Linear Recurrence Relations (2009) (9)
Complexity of the Bollobás–Riordan Polynomial. Exceptional Points and Uniform Reductions (2008) (9)
Teaching Logic for Computer Science: Are We Teaching the Wrong Narrative? (2015) (8)
Some observations on Uniform Reduction for properties invariant on the range of definable relations (1978) (8)
Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory (1981) (8)
Finitary sketches (1997) (8)
Connection Matrices for MSOL-Definable Structural Invariants (2009) (7)
Complexity of the Bollobás-Riordan Polynomial (2008) (7)
Invariant Definability and P/poly (1998) (7)
Mental images and the architecture of concepts (1988) (7)
On Average Case Complexity of SAT for Symmetric Distribution (1995) (7)
Compactness, Embeddings and Definability (2016) (7)
Language and Automata Theory and Applications (2012) (7)
Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas (2008) (7)
The Universal Edge Elimination Polynomial and the Dichromatic Polynomial (2011) (6)
Securable Quantifiers, κ-Unions and Admissible Sets (1975) (6)
Capturing Complexity Classes with Lindström Quantifiers (1994) (6)
A Graph Polynomial Arising from Community Structure (Extended Abstract) (2009) (6)
Incremental restructuring of relational schemas (1988) (6)
On the existence of polynomial time algorithms for interpolation problems in propositional logic (1988) (5)
Indistinguishability by Default (2005) (5)
On P-unique hypergraphs (2017) (5)
BCNF via Attribute Splitting (2012) (5)
Invariant Definability (Extended Abstract) (1997) (5)
On the complexity of generalized chromatic polynomials (2017) (5)
A logician's view of graph polynomials (2017) (5)
Notions of Sameness by Default and their Application to Anaphora, Vagueness, and Uncertain Reasoning (2008) (5)
{Delta}-logics and generalized quantifiers (1974) (5)
On Weakly Distinguishing Graph Polynomials (2018) (4)
Gandy's principles for mechanisms as a model of parallel computation (1988) (4)
Keeping logic in the trivium of computer science: a teaching perspective (2017) (4)
Optimal Spanners in Partial k-Trees (1993) (4)
A most general edge elimination graph polynomial (2007) (4)
Quantifying Over Countable Sets: Positive vs Stationary Logic (1978) (4)
Tropical Graph Parameters (2014) (4)
Can one design a geometry engine? On the (un)decidability of affine Euclidean geometries (2017) (4)
On sequences of polynomials arising from graph invariants (2017) (3)
Can one design a geometry engine? (2018) (3)
From Hilbert's Program to a Logic Toolbox (2007) (3)
Decidability of Finite Probablistic Propositional Dynamic Logics (1991) (3)
Abstract Embedding Relations (2016) (3)
A Representation Theorem for Holonomic Sequences Based on Counting Lattice Paths (2012) (3)
LOGICS CAPTURING RELATIVIZED COMPLEXITY CLASSES (1995) (3)
The impact of model theory on theoretical computer science (1995) (2)
Finiteness Conditions for Graph Algebras over Tropical Semirings (2014) (2)
The Fundamental Problem of Database Design (1997) (2)
Extensions and Limits of the Specker-Blatter Theorem (2022) (2)
Logics of Finite Hankel Rank (2015) (2)
Computer science logic : 17th International Workshop, CSL 2003, 12th annual conference of the EACSL, 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003 : proceedings (2003) (2)
Review: Jan Paredaens, Paul De Bra, Marc Gyssens, Dirk Van Gucht, The Structure of the Relational Database Model (1992) (1)
On the Tutte and Matching Polynomials for Complete Graphs (2021) (1)
MC-finiteness of restricted set partition functions (2023) (1)
Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width (2015) (1)
The Expressive Power of Side Effects in Prolog (1992) (1)
Computer Science Logic 17th International Workshop, Csl 2003, 12th Annual Conference of the Eacsl, and the 8th Kurt Gödel Colloquium, Kgc 2003 : Proceedings (2003) (1)
Computer Science Logic (2003) (1)
Hankel Matrices: From Words to Graphs (Extended Abstract) (2015) (1)
Clemens Lautemann: 1951-2005 An Obituary (2005) (1)
The Specker-Blatter theorem revisited: generating functions for definable classes of structures (2003) (1)
The Undecidability of Orthogonal and Origami Geometries (2018) (1)
Review: Heikki Mannila, Kari-Jouko Raiha, The Design of Relational Databases; Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases; Paris C. Kanellakis, Jan van Leeuwen, Elements of Relational Database Theory (1997) (1)
Semantic Equivalence of Graph Polynomials Definable in Second Order Logic (2016) (1)
Erratum to "Arity and Alternation in Second-Order Logic" (1998) (1)
Polynomials of Bounded Tree Width (Extended Abstract) (2000) (1)
The Reals Cannot be Characterized Topologically with Strictly Local Properties and Countability Axioms (1979) (1)
VR and HR Graph Grammars: A Common Algebraic Framework Compatible with Monadic Second-Order Logic (Extended Abstract) (2000) (1)
Weakly distinguishing graph polynomials on addable properties (2019) (1)
Chapter XVIII: Compactness, Embeddings and Definability (1985) (0)
Model theoretic methods in finite combinatorics : AMS-ASL joint special session, January 5-8, 2009, Washington, DC (2011) (0)
Book Review: Predicate Transformer Semantics. By Ernest G. Manes. (Cambridge University Press, 1992. 233pp. ISBN 0-521-42036-9. $39.95) (1993) (0)
Counting Finite Topologies (2023) (0)
Some Thoughts on Computational Models: From Massive Human Computing to Abstract State Machines, and Beyond (2021) (0)
Definability and Complexity of Graph Parameters (Invited Talk) (2012) (0)
INCREMENTAL MODEL CHECKING FOR DECOMPOSABLE (1995) (0)
Almost unimodal and real-rooted graph polynomials (2021) (0)
On the exact learnability of graph parameters: The case of partition functions (2016) (0)
Errata: Measuring the Expressive Power of Dynamic Logics: An Application of Abstract Model Theory (1981) (0)
0 D ec 2 01 7 On P-unique hypergraphs (0)
Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants (2008) (0)
Harary polynomials (2020) (0)
Can one design a geometry engine ? On the ( un ) decidability of certain affine Euclidean geometries (2018) (0)
Chapter XX: Abstract Embedding Relations (1985) (0)
The Ackermann Award 2006 (2006) (0)
Language and Automata Theory and Applications (2016) (0)
The exact complexity of the Tutte polynomial (2019) (0)
Tuesday ( Including celebration of Tutte centenary ) (2017) (0)
Update languages vs. query languages (1992) (0)
Modernism, Fiction and Mathematics (2019) (0)
Generalizing Parikh’s Theorem (2011) (0)
The Ackermann Award 2007 (2007) (0)
Can one design a geometry engine? (2018) (0)
Formal Interactive Menu Design (1992) (0)
Axiomatizing Origami planes. (2020) (0)
ec 2 00 7 A Most General Edge Elimination Graph Polynomial (2007) (0)
Logic Colloquium '95 Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic, Haifa, Israel, August 9-18, 1995 (1998) (0)
Chapter XIX: Abstract Equivalence Relations (1985) (0)
Musician - A Music Processing and Synthesis System (1986) (0)
Abstract Equivalence Relations (2016) (0)
Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241) (2016) (0)
The Ackermann Award 2010 (2010) (0)
Application of Logic to Integer Sequences: A Survey (2010) (0)
To Yuri at 80 and More than 40 Years of Friendship (2020) (0)
Model Theory in Computer Science: My Own Recurrent Themes (2011) (0)
From Parikh's Theorem to Many-Sorted Spectra (2010) (0)
Hankel Matrices for Weighted Visibly Pushdown Automata (2015) (0)
The Ackermann Award 2008 (2008) (0)
Computability and Definability (2011) (0)
1995 European Summer Meeting of the Association for Symbolic Logic (1997) (0)
The Ackermann Award 2005 (2005) (0)
A representation theorem for (q-)holonomic sequences (2014) (0)
Remembering Ernst Specker (1920-2011) (2012) (0)
The Ackermann Award 2009 (2009) (0)
5 Conclusions and Further Research (1992) (0)
Topological Model Theory (2010) (0)
Foreword (2012) (0)

This paper list is powered by the following services:

Other Resources About Johann Makowsky

What Schools Are Affiliated With Johann Makowsky?

Johann Makowsky is affiliated with the following schools:

Johann Makowsky's Academic­Influence.com Rankings