Definability of Combinatorial Functions and Their Linear Recurrence Relations (2009)
We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan...
The Enumeration of Vertex Induced Subgraphs with respect to the Number of Components (2008)
Tittmann, P., Averbouch, I., Makowsky, J. A.
Inspired by the study of community structure in connection networks, we introduce the graph polynomial $Q(G;x,y)$, the bivariate generating function which counts the number of connected components in...
E. Fischer, J. A. Makowsky, Subject Classi Cation
Combinatorics related algorithms and complexity, Generating functions, Automata, logic and computability, Graph theory, Abstract. In this paper we study the generating function of classes of graphs...
Computing graph polynomials on graphs of bounded clique-width (2008)
J. A. Makowsky, Udi Rotics, Ilya Averbouch, Benny Godlin
Abstract. We discuss the complexity of computing various graph polynomials of graphs of fixed clique-width. We show that the chromatic polynomial, the matching polynomial and the two-variable...
ENCOUNTERS WITH A. MOSTOWSKI (2008)
Abstract. We trace our encounters with Prof. A. Mostowski, in person and in his papers. It turns out that he and his papers left a continuous mark on my own work, from its very beginning, and till...
Kai Brünnler, Csl (m. Baaz, J. A. Makowsky, Lecture Notes, Stig Andur Pedersen, Uwe Scheffler, ...
ch/~kai/Papers/phd.pdf. 4., Cut elimination inside a deep inference system for classical predicate logic, Studia Logica 82 (2006), no. 1,
Abstract. (English) We consider various classes of graph polynomials and study their computational complexity. Our main focus is on Farrell polynomials and generating functions of graph properties....
Abstract. Relational structures oer a common framework to handle graphs and hypergraphs of various kinds. Operations like disjoint union, creation of new relations by means of quantier-free formulas,...
Decidability Questions for Finite Probabilistic Propositional Dynamic Logic (2007)
Revised Version, M. L. Tiomkin, J. A. Makowsky
: This paper deals with various versions of finite propositional probabilistic dynamic logic. Besides the logics previously introduced in the literature [Fe, Ko79, Ko83] we present some natural...
Polynomials of Bounded Tree-Width (Extended Abstract) (2007)
Johann A. Makowsky, Klaus Meer, J. A. Makowsky, K. Meer
Abstract. We introduce a new sparsity conditions on multivariate polynomials in n variables (over some ring R) and show that under this condition many otherwise intractable computational problems...
Abstract. We study the parametrized complexity of the knot (and link) polynomials known as Jones polynomials, Kauffman polynomials and Homfly-polynomials. It is known that computing these polynomials...
From a zoo to a zoology: Towards a general theory of graph polynomials (2007)
Abstract. We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte...
The complexity of multivariate matching polynomials (2007)
Ilia Averbouch, J. A. Makowsky
We study various versions of the univariate and multivariate matching and rook polynomials. We show that there is most general multivariate matching polynomial, which is, up the some simple...
Polynomial invariants of graphs and totally categorical theories (2006)
Abstract. In the analysis of the structure of totally categorical first order theories, the second author showed that certain combinatorial counting functions play an important role. Those functions...
From a zoo to a zoology: Descriptive complexity for graph polynomials (2006)
Abstract. We outline a general theory of graph polynomials which covers all the examples we found in the vast literature, in particular, the chromatic polynomial, various generalizations of the Tutte...
On spectra of sentences of monadic second order logic with counting (2004)
We show that the spectrum of a sentence φ in Counting Monadic Second Order Logic (CMSOL) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided...
Tree-width and the monadic quantifier hierarchy (2003)
It is well known that on classes of graphs of bounded tree width every monadic second order property is decidable in polynomial time. The converse is not true without further assumptions. It follows...
Outline of Course Lecture 1: Prelude: the overall picture. (2001)
Logical definability and computability on finite structures Lecture 2: Ehrenfeucht-Fra"iss'e games Feferman-Vaught Theorem and its ramifications Two applications Lecture 3: Inductive...
B. Courcelle, J. A. Makowsky, U. Rotics
We discuss the parametrized complexity of counting and evaluation problems on graphs where the range of counting is definable in Monadic Second Order Logic. We show that for bounded tree-width these...
PRELUDE Outlook References (2000)
Combinatorial algorithms ffl Deciding properties of a graph Connected, cycle-free, hamiltonian, 3-colorable ffl Finding configurations in a graph Connected component, (hamiltonian) cycle, 3-coloring...
Colored Tutte Polynomials and Kauffman Brackets for Graphs of Bounded Tree Width (2000)
. Jones polynomials and Kauffman polynomials are the most prominent invariants of knot theory. For alternating links, they are easily computable from the Tutte polynomials by a result of...
. We present a unified framework for the study of the complexity of counting functions and multivariate polynomials such as the permanent and the hamiltonian in the computational model of Blum, Shub...
) J.A. Makowsky 12? and K. Meer 3 1 Department of Computer Science Technion{Israel Institute of Technology Haifa, Israel e{mail: janos@@cs.technion.ac.il 2 Department of Mathematics Swiss Federal...
Polynomials of Bounded Tree Width (Extended Abstract) (2000)
) J.A. Makowsky 12? and K. Meer 3 1 Department of Computer Science Technion{Israel Institute of Technology Haifa, Israel e{mail: janos@cs.technion.ac.il 2 Department of Mathematics Swiss Federal...
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width (1999)
B. Courcelle, J.A. Makowsky, U. Rotics
Hierarchical decompositions of graphs are interesting for algorithmic purposes. There are several types of hierarchical decompositions. Tree decompositions are the best known ones. On graphs of...
Invariant Definability and P/poly (1999)
. We look at various uniform and non-uniform complexity classes within P=poly and its variations L=poly, NL=poly, NP=poly and PSpace=poly, and look for analogues of the Ajtai-Immerman theorem which...
B. Courcelle, J.A. Makowsky, U. Rotics
. We discuss the parametrized complexity of enumeration and evaluation problems on graphs definable in Monadic Second Order Logic. We show that for fixed tree width, these problems are solvable in...
B. Courcelle, J.A. Makowsky, U. Rotics
Graphs of clique-width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In...
Dependency Preserving Refinements and the Fundamental Problem of Database Design (1998)
. We introduce a new point of view into database schemes by applying systematically an old logical technique: translation schemes, and their induced formula and structure transformations. This allows...
B. Courcelle, J.A. Makowsky, U. Rotics
. We discuss the parametrized complexity of enumeration and evaluation problems on graphs definable in Monadic Second Order Logic. We show that for fixed tree width, these problems are solvable in...
On the Clique-Width of Graphs with Few P 4 s (1998)
Babel and Olariu (1995) introduced the class of (q; t) graphs in which every set of q vertices has at most t distinct induced P 4 s. Graphs of clique-width at most k were introduced by Courcelle,...
Views and Updates over Distributed Databases (Extended Abstract) (1998)
setting Assume we are given two undirected finite graphs A 1 = hVA1 ; EA1 ; PA1 i and A 2 = hVA2 ; EA2 ; QA2 i, where VA i denotes a set of vertices, EA i denotes a set of edges and PA1 ; QA2 are one...
Algebraic and Descriptive Complexity of Combinatorial . . . (1997)
J.A. Makowsky, M. Krynicki, M. Mostowski, L. W. Szczerba, Kluwer Academic
s Int. Conf. Number Theoretic and Algebraic Methods in Computer Science, Moscow, Russia, 1993, 62-65. (See 6.iv.) (ii) J. von zur Gathen and I. E. Shparlinski, Finding points on curves over finite...
Invariant Definability (Extended Abstract) (1997)
) J.A. Makowsky ? Department of Computer Science Technion---Israel Institute of Technology IL-32000 Haifa, Israel janos@cs.technion.ac.il Abstract. We define formally the notion of invariant...
The Complexity of Schur Functions in Characteristic 2 (1997)
We study the algebraic complexity of the Hamiltonian polynomials HCn (and of some of its generalizations) over finite fields k of characteristic 2. We show that when restricted to unitary matrices,...
Invariant definability and P/poly (Extended Abstract) (1997)
This article was processed using the L
Arity and Alternation in Second Order Logic (1996)
. We investigate the expressive power of second order logic over finite structures, when two limitations are imposed. Let SAA(k;n) (AA(k;n)) be the set of second order formulas such that the arity of...
Translation Schemes and the Fundamental Problem of Database Design (1996)
. We introduce a new point of view into database schemes by applying systematically an old logical technique: translation schemes, and their induced formula and structure transformations. This allows...
Dependency preserving refinements of relational database schemes (Extended Abstract) (1996)
, April 1996 Abstract. We introduce a new point of view into database schemes by applying systematically an old logical technique: translation schemes, and their induced formula transformation. This...
Logics Capturing Relativized Complexity Classes Uniformly (1995)
. We introduce the notion of a logic capturing a relativized complexity class uniformly by treating both generalized quantifiers and oracles as indeterminates and requiring that the correspondence be...
The Impact of Model Theory on Theoretical Computer Science (1995)
J.A. Makowsky, In D. Gabbay, M. Sharir, J. Hopcroft
equivalence relations. In Model-Theoretic Logics, Perspectives in Mathematical Logic, chapter 19. Springer Verlag, 1985. [Mos74] Y. Moschovakis. Elementary Induction on Abstract Structures. Studies...
Incremental Model Checking for Decomposable Structures (1995)
. Assume we are given a transition system which is composed from several well identified components. We propose a method which allows us to reduce the model checking of formulas in the complex system...
Incremental Model Checking for Fixed Point Properties on Decomposable Structures (1995)
, April 1995 Abstract. Assume we are given a transition system which is composed from several well identified components. We propose a method which allows us to reduce the model checking of Safety,...
Computable Quantifiers and Logics over Finite Structures (1995)
J.A. Makowsky, Y.B. Pnueli, M. Krynicki, M. Mostowski, L. W. Szczerba
We explore the notion of computable quantifiers over finite structures and use them to give a unified treatment of the theory of computable queries in databases and logics capturing complexity...
Capturing Complexity Classes with Lindström Quantifiers (1994)
J.A. Makowsky, Lindstrom Logics
. We report on our efforts of unifying Descriptive Complexity Theory and Logic in the framework of axiomatic definitions of both Logics and Complexity Classes. (Joint work with Y.B. Pnueli) In the...
Oracles and Quantifiers (1994)
. We describe a general way of building logics with Lindstrom quantifiers, which capture regular complexity classes on ordered structures with polysize reductions. We then extend this method so as to...
Optimal Spanners in Partial k-Trees (1993)
Assume you have a problem K which is NP--hard in general, but in P for a certain class of graphs G. Let PatchG be a class of graphs which are `patched' together from graphs from G. Is membership...
Model Theory and Computer Science: An Appetizer (1992)
Oxford University Press 1992. We first review the main developments of model theory as it evolved as a branch of mathematical logic and examine which developments have a potential for research in...
The Ehrenfeucht-Fraïssé Games for Transitive Closure (1992)
We present in this paper Ehrenfeucht--Fraiss'e games for the transitive closure logics DTC, TC and ATC. Although the existence of such games for logics with generalized quantifiers was known...
Programming Reactive Systems with Statecharts (Extended Abstract) (1991)
) Abstract In spite of the progress in software engineering practice over the recent years, the synthesis and implementation of real-time applications remains a challenging task. In this article, we...
Query Languages for Hierarchic Dadabases (1990)
Elias Dahlhaus, J.A. Makowsky, Ak S. Abiteboul, P. Kanellakis, Abddmz M. Atkinson, F. Bancilhon, ...
recursion as a foundation for the theory of algorithms, in: Computation and Proof Theory, M.M. Richter et al. eds., LNM vol. 1104, Springer, Berlin-Heidelberg 1984 pp. 289-362. [No78] D. Norman, Set...