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
The PC of GRATRA 2000 has selected this paper
to receive the GRATRA 2000 award for the best theoretical
paper in the area of graph transformations.
From Hilbert's Program to a Logic Toolbox.
2009
"Definability of Combinatorial Functions and
Their Linear Recurrence Relations",
preprint, submitted to the Yuri Gurevich 70 Festschrift
"Fifty Years of the Spectrum Problem: Survey and New Results"
preprint, submitted to the Bulletin of Symbolic Logic, July 2009
"The Enumeration of Vertex Induced Subgraphs with Respect to the
Number of Components"
preprint,
arXive version,
arxiv.org/pdf/0812.4147
"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.
"Connection Matrices for MSOL-definable Structural Invariants"
preprint,
2008
2007
"Graph polynomials: From recursive definitions to subset expansion formulas",
arXiv version version December 7, 2008,
From a Zoo to a Zoology:
Towards a General Theory of
Graph Polynomials.
download .
Published paper .
Theory of Computing Systems, 43 (2008), pp. 542-562.
Special issue of selected papers from CiE06.
This is a largely extended version of the conference
paper from CiE06.
"On Counting Generalized Colorings"
Submitted version,
Published version,
CSL 2008,
17th EACSL Annual Conference on
Computer Science Logic
15th-20th September 2008,
Bertinoro, Italy
M. Kaminski and S. Martini (Eds.): LNCS 5213, pp. 339-353, 2008.
"A Most General Edge Elimination Polynomial"
Published version,
WG 2008,
34th International Workshop on Graph-Theoretic Concepts in Computer Science.
30 June - 2 July 2008, Durham University, U.K.
H. Broersma et al. (Eds.): WG 2008, LNCS 5344, pp. 31-42, 2008.
"Evaluations of Graph Polynomials"
Published version,
WG 2008,
34th International Workshop on Graph-Theoretic Concepts in Computer Science.
30 June - 2 July 2008, Durham University, U.K.
H. Broersma et al. (Eds.): WG 2008, LNCS 5344, pp. 183-194, 2008.
"From Parikh's Theorem to Many-Sorted 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.
"Complexity of the Bollobas-Riordan
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 7-12, 2008, Moscow, Russia,
Computer Science - Theory and Applications, E.A. Hirsch et al. (Eds.), LNCS 5010, pp. 86-98, 2008.
Notions of sameness by default and their application
to anaphora, vagueness and uncertain reasoning
Linear Recurrence Relations for Graph Polynomials,
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. 261-277.
Counting truth assignments of formulas of bounded tree-width or clique-width
Published paper ,
Offprint .
"A most general edge elimination graph polynomial""
submitted,
arXiveversion.
The complexity of matching polynomials
Full paper .
The quantum FFT can be classically simulated.
posting
at arXiv:quant-ph/0611156v1, 14. Nov. 2006
2006
Polynomial invariants of graphs and totally categorical theories
Preprint,
Modenet-version.
Computing graph polynomials on graphs of bounded clique-width
Full paper .
In:
Proceedings of WG06, H. Bodlaender et al. eds, LNCS 4271 (2006)
191-204.
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. 330-341.
2005
Coloured Tutte Polynomials and Kauffman Brackets
for Graphs of Bounded Tree Width
Abstract ,
Journal ps-version , latest revision: February 2003.
Journal pdf-version .
Discrete Applied Mathematics . 145 (2005) pp. 276-290
Extended Abstract ,
Proceedings of the 12th Annual ACM-SIAM Symposium
on Discrete Algorithms, Washington DC, 2001,
pp. 487-495.
2004
On Spectra of Sentences of Monadic Second Order Logic
with Counting
Journal paper, 26 p.
dvi-file, .
ps-file, .
pdf-file, .
Journal of Symbolic Logic, 69.3 (2004) pp. 617-640
Algorithmic Uses of the Feferman-Vaught Theorem ,
Annals of Pure and Applied Logic, 126 (1-3) April 2004,
pp. 159-213.
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:
ps-file, or
pdf-file,
52p.
On the algebraic complexity of some families of
coloured Tutte polynomials,
full paper ps-version,
full paper pdf-version,
(revised October 2002),
Advances in Applied Mathematics, Special issue on Tutte polynomials.
32.1-2 (2004) pp. 327-349.
2003
NCE graph grammars and clique-width
Extended Abstract ,
in:
Graph-Theoretic Concepts in Computer Science,
Springer Lecture Notes in Computer Science,
Volume: 2880,
(October (2003) pp 237-248
The Specker-Blatter 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. 90-101.
The Specker-Blatter theorem does not hold for quaternary relations
full paper
,
Last revision 07.03.2003.
Journal of Combinatorial Theory Series A
103 (2003), 121-136.
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. 160-176.
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. 742-756
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) 157-170.
2002
Fusion in Relational Structures and the
Verification
of Monadic Second-Order Properties,
Full paper
,
Mathematical Structures in Computer Science (MSCS)
12 (2002) pp. 203-235.
Polynomials of bounded tree width,
Full version of extended abstract
presented at FPSAC'00
(cf. below).
2001
Discrete Applied mathematics, vol. 108, No. 1-2 (2001), pp. 23-52.
Abstract
or
2000
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.
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. 692-703.
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. 399-410.
Linear Time Solvable Optimization Problems on
Graphs of Bounded Clique Width,
Theory of Computing Systems, Volume 33 - Number 2 (2000) pages 125-150
Abstract
or
1999
VR and HR Graph Grammars:
A Common Algebraic Framework Compatible with
Monadic Second Order Logic
Extended Abstract
,
November 1999 , accepted to
GRATRA'2000
,
accepted for publication in the proceedings
of CSL'98, LNCS 1999.
Abstract
or
Final paper
, revised January 1999.
International Journal of Foundations of Computer Science,
10 (1999) pp. 329-348.
1998
Review of
Oswald Wiener, Manuel Bonik und Robert Hoedicke,
Eine Elementare Einfuerung in die Theorie der
Turing--Maschinen, Springer, Wien und New York, 1998,
vii + 283 Seiten, mit Diskette
Puplished in
Der Standard,
Vienna, 31. Juli 1998
Published version
Abstract
, presented to
THE SECOND PALESTINIAN INTERNATIONAL CONFERENCE ON MATHEMATICS
August 19-22, 1998
Birzeit, Palestine
1997
Computing Permanents over Fields of Characteristic 3:
Where and Why it Becomes Difficult,
(December 1997).
Abstract
or
Full paper
(revised version in preparation).
The Complexity of Schur Functions in
Finite Fields of Characteristic 2 (May 1997, revised December 1997).
Abstract
or
Full paper
(revised version in preparation).
The Complexity of Schur Functions over
Finite Fields (May 1997),
Research proposal for the Candidacy examination.
Full text
Supervisor:
J.A. Makowsky
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. 277-312.
(Revised version of:
Translation Schemes and the
Fundamental problem of Database Design,
Conceptual Modeling - ER'96, B. Thalheim (ed.),
LNCS vol. 1157 (1996) pp. 5-26)
Abstract
or
Full paper
Abstract
or
Full paper
Extensions for open default theories via the domain closure assumption
(Revised March 1997,)
Logic and Computation, vol. 8.2, April 1998, pp 169-187
Abstract
or
Full paper
Restrictions of Minimum Spanner Problems,
Information and Computation, 136 (1997), pp.
146-164.
Abstract
or
Full paper
Finitary Sketches (completed in January 1996),
Journal of Symbolic Logic, 62.3 (1997), pp. 699-707.
Abstract
or
Full paper
1996
The Design of Relational Databases by
Heikki Mannila and Kari--Jouko 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. 1073-1156,
North Holland 1990.
Journal of Symbolic Logic , vol. 62.1 (1997), pp. 324-326.
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. 5-26)
Conference paper
(to appear in Logic and Random Structures,
DIMACS Series in Discrete Mathematics and Theoretical
Computer Science, 1996)
Mathematics as a literary genre.
Talk given at the
First International Conference on
Argumentation in Teaching, Sciences and the Humanities.
Haifa, 26-27 May 1996.
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.
Computing permanents in fields of characteristic 3.
Extended abstract, published in FOCS'96, pp. xx-yy.
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
Incremental Model Checking for Fixed Point Properties
on Decomposable Structures.
(Revised version, April 1995, 15 pp.)
Unpublished, see 1997
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. 540-551
)
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. 463-479
)
1994
Arity vs Alternation in Second Order Logic,
14 pp., May 1994
(Published in:
Annals of Pure and Applied Logic, vol. 78 (1-3), 1996, pp.
189-202,
Conference version in:
Logical Foundations of Computer Science--St. Petersburg 1994,
LNCS, vol. 813, 1994, pp. 240-252
)
On Average Case Complexity of {\bf SAT}
for Symmetric Distributions.
(Revised version of TR739, published in:
Logic and Computation, vol. 5.1 (1995), pp. 71-92
)
Oracles and Quantifiers.
34 pp., May 1994
(Expanded version of TR785, published in
CSL'93, LNCS, vol. 832, 1994, pp. 189-222
)
1993
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. 313-357.
)