J.A. Makowsky and Collaborators
Available Technical Reports and Preprints
Last updated: 06.02.2010
Back to Homepage
Invited Lectures
Slides of lectures and talks 19972010
NEW: Wellington, Asian Logic Conference 2011
The difficult point conjecture for graph polynomials
Slides,
NEW: Paris, Logic Seminar, February 2010
Application of logic to generating functions: Holonomic Sequences
Slides,
NEW: Invited lecture at CiE08 and ICLA09
and Workshop at Hranicni Zamecek
Intriguing graph polynomials
Slides,
NEW: Invited lecture at LPAR07, Yerevan, October 2007::
From Hilbert's Program to a Logic Toolbox.
Slides.
NEW: Invited lecture at ISAIM 2008, Fort Lauderdale, January 2008
From Hilbert's Program to a Logic Toolbox.
Text version
Text version,
expanded in revised,
Oct 2008,
to appear in the special volume of
Annals of Mathematics and Artificial Intelligence
to honor the 65th birthday of Victor Marek
edited by Michael Kaminski and
Miroslaw Truszczynski
2009
 NEW: T. Kotek and J.A. Makowsky
"Definability of Combinatorial Functions and
Their Linear Recurrence Relations",
preprint, submitted to the Yuri Gurevich 70 Festschrift
 NEW: A. Durand, N.D. Jones, J.A. Makowsky and M. More
"Fifty Years of the Spectrum Problem: Survey and New Results"
preprint, submitted to the Bulletin of Symbolic Logic, July 2009
 NEW: P. Tittmann, I. Averbouch and J.A. Makowsky
"The Enumeration of Vertex Induced Subgraphs with Respect to the
Number of Components"
preprint,
arXive version,
arxiv.org/pdf/0812.4147
 REVISED: I. Averbouch, B. Godlin and J.A. Makowsky,
"An Extension of the bivariate chromatic polynomial"
download, Revised and expanded version of
"A Most General Edge Elimination Polynomial", to appear in the
European Journal of Combinatorics.
 NEW: J.A. Makowsky
"Connection Matrices for MSOLdefinable Structural Invariants"
preprint,
Published version,
in LNCS (LNAI) 5378, Proceedings of the
Third Indian Conference on Logic and its Applications,
January 711, 2009,
Chennai, India
ICLA 2009,
2008
 NEW: B. Godlin, E. Katz and J.A. Makowsky
"Graph polynomials: From recursive definitions to subset expansion formulas",
arXiv version version December 7, 2008,
 PUBLISHED:
J.A. Makowsky
From a Zoo to a Zoology:
Towards a General Theory of
Graph Polynomials.
download .
Published paper .
Theory of Computing Systems, 43 (2008), pp. 542562.
Special issue of selected papers from CiE06.
This is a largely extended version of the conference
paper from CiE06.
 PUBLISHED: T. Kotek, J.A. Makowsky and B. Zilber
"On Counting Generalized Colorings"
Submitted version,
Published version,
CSL 2008,
17th EACSL Annual Conference on
Computer Science Logic
15th20th September 2008,
Bertinoro, Italy
M. Kaminski and S. Martini (Eds.): LNCS 5213, pp. 339353, 2008.
 PUBLISHED: I. Averbouch, B. Godlin and J.A. Makowsky,
"A Most General Edge Elimination Polynomial"
Published version,
WG 2008,
34th International Workshop on GraphTheoretic Concepts in Computer Science.
30 June  2 July 2008, Durham University, U.K.
H. Broersma et al. (Eds.): WG 2008, LNCS 5344, pp. 3142, 2008.
 PUBLISHED: B. Godlin, T. Kotek and J.A. Makowsky,
"Evaluations of Graph Polynomials"
Published version,
WG 2008,
34th International Workshop on GraphTheoretic Concepts in Computer Science.
30 June  2 July 2008, Durham University, U.K.
H. Broersma et al. (Eds.): WG 2008, LNCS 5344, pp. 183194, 2008.
 NEW (last revised 17.5.2008): J.A. Makowsky,
"From Parikh's Theorem to ManySorted Spectra"
Full paper.
To appear in: "Logic at the Crossroads: An Interdisciplinary View", vol. II,
A. Gupta, R. Parikh and J. van Benthem, eds, Allied Publishers Pvt,
New Delhi.
For vol. I look
here.
 PUBLISHED:
Markus Blaeser, Holger Dell, J.A. Makowsky,
"Complexity of the BollobasRiordan
Polynomial: Exceptional points and uniform reductions"
Offprint,
Published version,
Journal version, ,
submitted to Special Issue of ToCS with selected CSR'08 papers.
3rd International Computer Science Symposium in Russia (CSR 2008)
June 712, 2008, Moscow, Russia,
Computer Science  Theory and Applications, E.A. Hirsch et al. (Eds.), LNCS 5010, pp. 8698, 2008.
 PUBLISHED:
A. Cohen, M. Kaminski and J.A. Makowsky
Notions of sameness by default and their application
to anaphora, vagueness and uncertain reasoning
Full paper.
Journal of Logic, Language and Information
Online first .
 PUBLISHED: (last revised 14.10.07):
E. Fischer and J.A. Makowsky
Linear Recurrence Relations for Graph Polynomials,
Offprint,
Published paper .
Special volume
in honour of
Boris (Boaz) A. Trakhtenbrot on the occasion of his 85th birthday.
LNCS 4800 (2008) pp. 266279
 PUBLISHED: (last revised 04.03.07):
J.A. Makowsky
Encounters with A. Mostowski
Full paper .
70 Years of Foundational
Studies, In memoriam of Andrzej Mostowski.
W. Marek and M. Srebrny editors.
IOS Press. 2008. pp. 261277.
 PUBLISHED:
E. Fischer, J.A. Makowsky and E.R. Ravve,
Counting truth assignments of formulas of bounded treewidth or cliquewidth
Published paper ,
Offprint .
Full paper .
Discrete Applied Mathematics,
Discrete Applied Mathematics, 156 (2008), pp. 511529
2007
 POSTED:
I. Averbouch, B. Godlin and J.A. Makowsky,
"A most general edge elimination graph polynomial""
submitted,
arXiveversion.
 PREPRINT: (last revised 02.03.07):
I. Averbouch and J.A. Makowsky
The complexity of matching polynomials
Full paper .
 POSTED::
D. Aharonov, Z. Landau and J.A. Makowsky
The quantum FFT can be classically simulated.
posting
at arXiv:quantph/0611156v1, 14. Nov. 2006
2006
 POSTED: (last revised December 12, 2006):
J.A. Makowsky and B. Zilber
Polynomial invariants of graphs and totally categorical theories
Preprint,
Modenetversion.
 PUBLISHED:
J.A. Makowsky, U. Rotics, I. Averbouch and B. Godlin,
Computing graph polynomials on graphs of bounded cliquewidth
Full paper .
In:
Proceedings of WG06, H. Bodlaender et al. eds, LNCS 4271 (2006)
191204.
 PUBLISHED:
J.A. Makowsky
From a Zoo to a Zoology:
Descriptive Complexity for Graph Polynomials.
Full paper .
In:
Arnold Beckmann, Ulrich Berger, Benedikt Loewe, and John V Tucker
(eds.): Logical Approaches to Computational Barriers, Second
Conference on Computability in Europe, CiE 2006, Swansea, UK, July
2006, Proceedings, Lecture Notes in Computer Science volume 3988,
pp. 330341.
2005
 PUBLISHED:
J.A. Makowsky,
Coloured Tutte Polynomials and Kauffman Brackets
for Graphs of Bounded Tree Width
Abstract ,
Journal psversion , latest revision: February 2003.
Journal pdfversion .
Discrete Applied Mathematics . 145 (2005) pp. 276290
Extended Abstract ,
Proceedings of the 12th Annual ACMSIAM Symposium
on Discrete Algorithms, Washington DC, 2001,
pp. 487495.
2004
 PUBLISHED:
E. Fischer and J.A. Makowsky
On Spectra of Sentences of Monadic Second Order Logic
with Counting
Journal paper, 26 p.
dvifile, .
psfile, .
pdffile, .
Journal of Symbolic Logic, 69.3 (2004) pp. 617640
 PUBLISHED:
J.A. Makowsky
Algorithmic Uses of the FefermanVaught Theorem ,
Annals of Pure and Applied Logic, 126 (13) April 2004,
pp. 159213.
Special issue: Provinces of logic determined. Essays in the memory of
Alfred Tarski. Parts I, II and III Edited by Z. Adamowicz, S.
Artemov, D. Niwinski, E. Orlowska, A. Romanowska and J. Wolenski
Earlier versions:
psfile, or
pdffile,
52p.
 PUBLISHED:
M. Lotz and J.A. Makowsky
On the algebraic complexity of some families of
coloured Tutte polynomials,
full paper psversion,
full paper pdfversion,
(revised October 2002),
Advances in Applied Mathematics, Special issue on Tutte polynomials.
32.12 (2004) pp. 327349.
2003
 PUBLISHED:
A. Glikson and J.A. Makowsky
NCE graph grammars and cliquewidth
Extended Abstract ,
in:
GraphTheoretic Concepts in Computer Science,
Springer Lecture Notes in Computer Science,
Volume: 2880,
(October (2003) pp 237248
 PUBLISHED:
E. Fischer and J.A. Makowsky
The SpeckerBlatter Theorem revisited: Generating functions
for definable classes of strcutures.
Extended abstract
, with many appendices.
Extended abstract
, conference version, without appendices.
Last revision 22.04.2003,
accepted for COCOON'03.
in Computing and Combinatorics,
Proceedings of the
9th Annual International Conference, COCOON 2003,
LNCS vol. 2697 (2003) pp. 90101.
 PUBLISHED:
E. Fischer
The SpeckerBlatter theorem does not hold for quaternary relations
full paper
,
Last revision 07.03.2003.
Journal of Combinatorial Theory Series A
103 (2003), 121136.
 PUBLISHED:
J.A. Makowsky and J.P. Marino
Farrell polynomials on graphs of bounded tree width
full paper
,
presented at FPSAC'01,
Special issue of FPSAC'01 papers,
Advances in Applied Mathematics
30 (2003) pp. 160176.
 PUBLISHED:
J.A. Makowsky and J.P. Marino
The parametrized complexity of knot polynomials
Revised version (April 7, 2002) of
On the tree width of knot and link diagrams
full paper
Special issue on Paramterized Computation and Complexity,
JCSS
67.4 (2003) pp. 742756
 PUBLISHED:
J.A. Makowsky and J.P. Marino
Treewidth and the monadic quantifier hierarchy
full paper
(last revision, March 2002),
Special issue
in honour of A.O. Slissenko's 60th birthday.
of Theoretical Computer Science, 303 (2003) 157170.
2002
 PUBLISHED:
B. Courcelle and J.A. Makowsky,
Fusion in Relational Structures and the
Verification
of Monadic SecondOrder Properties,
Full paper
,
Mathematical Structures in Computer Science (MSCS)
12 (2002) pp. 203235.
 PUBLISHED:
J.A. Makowsky and K. Meer,
Polynomials of bounded tree width,
Full paper
,
in Foundations of Computational Mathematics,
Proceedings of the Smalefest 2000, Felipe Cucker and J. Maurice Rojas, edts.,
World Scientific 2002, pp. 211250.
Full version of extended abstract
presented at FPSAC'00
(cf. below).
2001
 PUBLISHED:
B. Courcelle, J.A. Makowsky and U. Rotics,
On the Fixed Parameter Complexity of
Graph Enumeration Problems Definable in Monadic Second
Order Logic,
Discrete Applied mathematics, vol. 108, No. 12 (2001), pp. 2352.
Abstract
or
Full paper
(Revised version May 2000)
2000
 PREPRINT:
B. Courcelle and J.A. Makowsky,
Operations on Relational Structures and their Compatability
with Monadic Second Order Logic,
Full paper
, accepted for publication in
Mathematical Structures in Computer Science (MSCS)
(July 2000).
This is the full version of the GRATRA paper below.
A revised and mostly shortened versions with
changed title is to be
found
here
. See also under the 2001 entries.
 PUBLISHED:
J.A. Makowsky and K. Meer,
Polynomials of Bounded Tree Width
Extended Abstract ,
,
In: Formal Power Series and Algebraic Combinatorics,
Porceedings of
the
12th International Conference, FPSAC'00, Moscow, Russia, June 2000,
D. Krob, A.A. Mikhalev and A.V. Mikhalev eds.,
Springer, 2000, pp. 692703.
 PUBLISHED:
J.A. Makowsky and K. Meer,
On the Complexity of Combinatorial and Metafinite Generating Functions
of Graph Properties in the Computational Model of Blum, Shub and
Smale
Extended Abstract , in the proceedings of
Computer Science Logic , 14th International Workshop,
CSL'2000,
,
Annual Conference of the EACSL, Fischbachau, Germany, August 2000,
Peter G. Clote and Helmut Schwichtenberg, edts.,
LNCS 1862, pp. 399410.
 PUBLISHED:
B. Courcelle, J.A. Makowsky and U. Rotics,
Linear Time Solvable Optimization Problems on
Graphs of Bounded Clique Width,
Theory of Computing Systems, Volume 33  Number 2 (2000) pages 125150
Abstract
or
Full paper,
Full paper,
revised version, Aug 1999
Journal link
1999
1998

J.A. Makowsky,
Zen oder die Kunst eine Turing Maschine zu warten,
Review of
Oswald Wiener, Manuel Bonik und Robert Hoedicke,
Eine Elementare Einfuerung in die Theorie der
TuringMaschinen, Springer, Wien und New York, 1998,
vii + 283 Seiten, mit Diskette
Puplished in
Der Standard,
Vienna, 31. Juli 1998
Published version

J.A. Makowsky,
Emancipatory aspects of Learning (and Teaching) Mathematics,
Abstract
, presented to
THE SECOND PALESTINIAN INTERNATIONAL CONFERENCE ON MATHEMATICS
August 1922, 1998
Birzeit, Palestine

J.A. Makowsky and E. Ravve,
Views and Updates over Distributed Databases,
June 1998,
Abstract
or
Extended Abstract

B. Courcelle, J.A. Makowsky and U. Rotics,
Linear Time Solvable Optimization Problems on
Graphs of Bounded Clique Width,
Extended abstract (Feb 98, revised August 1998), published in
Graph Theoretic Concepts in Computer Science,
WG'98,
SmoleniceCastle (close to Bratislava), June 18  20, 1998,
LNCS vol. 1517 (1998) pp. 116.

M. Frick, J.A. Makowsky and Y. Pnueli ,
Oracles and Lindstrom Quantifiers on Ordered Structures,
journal version of CSL93 and LCC94 papers (in revision),
1997

G. Kogan and J.A. Makowsky,
Computing Permanents over Fields of Characteristic 3:
Where and Why it Becomes Difficult,
(December 1997).
Abstract
or
Full paper
(revised version in preparation).

G. Kogan and J.A. Makowsky,
The Complexity of Schur Functions in
Finite Fields of Characteristic 2 (May 1997, revised December 1997).
Abstract
or
Full paper
(revised version in preparation).

G. Kogan
The Complexity of Schur Functions over
Finite Fields (May 1997),
Research proposal for the Candidacy examination.
Full text
Supervisor:
J.A. Makowsky

J.A. Makowsky and E. Ravve,
Dependency Preserving Refinements and the
Fundamental problem of Database Design (completed April 1997),
accepted for publication in Data and Knowledge Engineering
vol. 24 (1998) pp. 277312.
(Revised version of:
Translation Schemes and the
Fundamental problem of Database Design,
Conceptual Modeling  ER'96, B. Thalheim (ed.),
LNCS vol. 1157 (1996) pp. 526)
Abstract
or
Full paper

J.A. Makowsky,
Invariant Definability,
in
Computational Logic and Proof Theory,
Proceedings of the 5th Kurt G\"odel Colloquium,
KGC'97, Vienna, August 1997,
LNCS vol. 1289 (1997), pp. 186202.
Abstract
or
Full paper

M. Kaminski, J.A. Makowsky and M. Tiomkin,
Extensions for open default theories via the domain closure assumption
(Revised March 1997,)
Logic and Computation, vol. 8.2, April 1998, pp 169187
Abstract
or
Full paper

G. Venkatesan, U. Rotics, M.S. Madanlal,
J.A. Makowsky and C. Pandu Rangan,
Restrictions of Minimum Spanner Problems,
Information and Computation, 136 (1997), pp.
146164.
Abstract
or
Full paper

J. Adamek, P. Johnstone, J. Makowsky and J. Rosicky,
Finitary Sketches (completed in January 1996),
Journal of Symbolic Logic, 62.3 (1997), pp. 699707.
Abstract
or
Full paper
1996

E. Rosen,
Modal Logic over Finite Structures
(August 1996)

E. Rosen,
An existential fragment of second order logic,
(revised version, December 1996)

J.A. Makowsky,
Review of
The Design of Relational Databases by
Heikki Mannila and KariJouko R\"aih\"a,
Addison Wesley 1992, reprinted 1994, vii +318 pages
Foundations of Database by
Serge Abiteboul, Richard Hull and Victor Vianu,
Addison Wesley 1995, xviii + 685 pages
Elements of relational database theory by
Paris C. Kanellakis in:
Handbook of Theoretical Computer Science, Volume B
(Jan van Leeuwen ed.), pp. 10731156,
North Holland 1990.
Journal of Symbolic Logic , vol. 62.1 (1997), pp. 324326.

J.A. Makowsky and E. Ravve,
Translation Schemes and the Fundamental problem of Database
Design
(invited lecture)
(Published in:
Conceptual Modeling  ER'96, B. Thalheim (ed.),
LNCS vol. 1157 (1996) pp. 526)
Conference paper

E. Rosen, S. Shelah and S. Weinstein,
kuniversal finite graphs (Shelah 611),
(to appear in Logic and Random Structures,
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, 1996)

E. Graedel, M. Otto and E. Rosen,
Undecidability results on twovariable logics,

J.A. Makowsky,
Mathematics as a literary genre.
Talk given at the
First International Conference on
Argumentation in Teaching, Sciences and the Humanities.
Haifa, 2627 May 1996.

M. Kaminski, J.A. Makowsky and M. Tiomkin,
Extensions for open default theories via the domain closure assumption.
(Extended Abstract)
to appear in the proceedings of the
5th European Workshop on Logics in AI  JELIA'96,
Evora, Portugal, September 30th  October 4th 1996.

G. Kogan (written by M. Kaminski and J.A. Makowsky),
Computing permanents in fields of characteristic 3.
Extended abstract, published in FOCS'96, pp. xxyy.
Reports before 1996
Below is a selection of reports from before 1996.
For a complete list of available papers please consult
Publications of J.A. Makowsky
1995

J.A. Makowsky and E. Ravve,
Incremental Model Checking for Fixed Point Properties
on Decomposable Structures.
(Revised version, April 1995, 15 pp.)
Unpublished, see 1997

J.A. Makowsky and E. Ravve,
Incremental Model Checking
for Decomposable Structures.
(Revised version, April 1995, 16 pp.)
(Published in: MFCS'95,
Mathematical Foundations of Computer Science 1995,
J. Wiedermann and P. Hajek eds.,
Lecture Notes in Computer Science, vol. 969 (1995), pp. 540551
)

J.A. Makowsky and Y.B. Pnueli,
Logics Capturing Relativized Complexity Classes Uniformly.
17 pp., revised version, March 1995
(Published in:
Proceedings of LCC'94,
Logic and Computational Complexity, D. Leivant ed.,
Lecture Notes in Computer Science vol. 960, 1995, pp. 463479
)
1994

J.A. Makowsky and Y.B. Pnueli,
Arity vs Alternation in Second Order Logic,
14 pp., May 1994
(Published in:
Annals of Pure and Applied Logic, vol. 78 (13), 1996, pp.
189202,
Conference version in:
Logical Foundations of Computer ScienceSt. Petersburg 1994,
LNCS, vol. 813, 1994, pp. 240252
)

J. Makowsky and A. Sharell.
On Average Case Complexity of {\bf SAT}
for Symmetric Distributions.
(Revised version of TR739, published in:
Logic and Computation, vol. 5.1 (1995), pp. 7192
)

J.A. Makowsky and Y.B. Pnueli,
Oracles and Quantifiers.
34 pp., May 1994
(Expanded version of TR785, published in
CSL'93, LNCS, vol. 832, 1994, pp. 189222
)
1993

J. A. Makowsky and Y.B. Pnueli,
Computable Quantifiers and Logics over Finite Structures,
39 pp., February 1992
(Published in:
"Quantifiers: Logics, Models and Computation, Volume I",
M. Krynicki, M. Mostowski and L.W. Szczerba
eds., Kluwer Academic Publishers, 1995, pp. 313357.
)