Search Results

Documents authored by Makowsky, Johann A.

Document
DOI: 10.4230/LIPIcs.CSL.2024.26
Extensions and Limits of the Specker-Blatter Theorem

Authors: Eldar Fischer and Johann A. Makowsky

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
The original Specker-Blatter Theorem (1983) was formulated for classes of structures 𝒞 of one or several binary relations definable in Monadic Second Order Logic MSOL. It states that the number of such structures on the set [n] is modularly C-finite (MC-finite). In previous work we extended this to structures definable in CMSOL, MSOL extended with modular counting quantifiers. The first author also showed that the Specker-Blatter Theorem does not hold for one quaternary relation (2003). If the vocabulary allows a constant symbol c, there are n possible interpretations on [n] for c. We say that a constant c is hard-wired if c is always interpreted by the same element j ∈ [n]. In this paper we show: (i) The Specker-Blatter Theorem also holds for CMSOL when hard-wired constants are allowed. The proof method of Specker and Blatter does not work in this case. (ii) The Specker-Blatter Theorem does not hold already for 𝒞 with one ternary relation definable in First Order Logic FOL. This was left open since 1983. Using hard-wired constants allows us to show MC-finiteness of counting functions of various restricted partition functions which were not known to be MC-finite till now. Among them we have the restricted Bell numbers B_{r,A}, restricted Stirling numbers of the second kind S_{r,A} or restricted Lah-numbers L_{r,A}. Here r is an non-negative integer and A is an ultimately periodic set of non-negative integers.
Cite as

Eldar Fischer and Johann A. Makowsky. Extensions and Limits of the Specker-Blatter Theorem. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.CSL.2024.26,
  author =	{Fischer, Eldar and Makowsky, Johann A.},
  title =	{{Extensions and Limits of the Specker-Blatter Theorem}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.26},
  URN =		{urn:nbn:de:0030-drops-196694},
  doi =		{10.4230/LIPIcs.CSL.2024.26},
  annote =	{Keywords: Specker-Blatter Theorem, Monadic Second Order Logic, MC-finiteness}
}
Document
DOI: 10.4230/DagRep.6.6.26
Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241)

Authors: Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt

Published in: Dagstuhl Reports, Volume 6, Issue 6 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 16241 "Graph Polynomials: Towards a Comparative Theory". The area of graph polynomials has become in recent years incredibly active, with new applications and new graph polynomials being discovered each year. However, the resulting plethora of techniques and results now urgently requires synthesis. Beyond catalogues and classifications we need a comparative theory. The intent of this 5-day Seminar was to further a general theory of graph polynomials.
Cite as

Jo Ellis-Monaghan, Andrew Goodall, Johann A. Makowsky, and Iain Moffatt. Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241). In Dagstuhl Reports, Volume 6, Issue 6, pp. 26-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{ellismonaghan_et_al:DagRep.6.6.26,
  author =	{Ellis-Monaghan, Jo and Goodall, Andrew and Makowsky, Johann A. and Moffatt, Iain},
  title =	{{Graph Polynomials: Towards a Comparative Theory (Dagstuhl Seminar 16241)}},
  pages =	{26--48},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{6},
  editor =	{Ellis-Monaghan, Jo and Goodall, Andrew and Makowsky, Johann A. and Moffatt, Iain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.6.26},
  URN =		{urn:nbn:de:0030-drops-67266},
  doi =		{10.4230/DagRep.6.6.26},
  annote =	{Keywords: complexity, counting functions, graph colourings, graph homomorphisms, graph invariants, graph polynomials, matroid invariants, second order logic, topological graph theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.63
On the Exact Learnability of Graph Parameters: The Case of Partition Functions

Authors: Nadia Labai and Johann A. Makowsky

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study the exact learnability of real valued graph parameters f which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph H with vertex weights alpha and edge weights beta. M. Freedman, L. Lovasz and A. Schrijver have given a characterization of these graph parameters in terms of the k-connection matrices C(f,k) of f. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter f, the learner can ask for the values of f for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices C(f,k) of f. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of H and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.
Cite as

Nadia Labai and Johann A. Makowsky. On the Exact Learnability of Graph Parameters: The Case of Partition Functions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{labai_et_al:LIPIcs.MFCS.2016.63,
  author =	{Labai, Nadia and Makowsky, Johann A.},
  title =	{{On the Exact Learnability of Graph Parameters: The Case of Partition Functions}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.63},
  URN =		{urn:nbn:de:0030-drops-64750},
  doi =		{10.4230/LIPIcs.MFCS.2016.63},
  annote =	{Keywords: exact learning, partition function, weighted homomorphism, connection matrices}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2012.14
Definability and Complexity of Graph Parameters (Invited Talk)

Authors: Johann A. Makowsky

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
In this talk we survey definability and complexity results of graph parameters which take values in some ring or field R.
Cite as

Johann A. Makowsky. Definability and Complexity of Graph Parameters (Invited Talk). In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 14-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{makowsky:LIPIcs.CSL.2012.14,
  author =	{Makowsky, Johann A.},
  title =	{{Definability and Complexity of Graph Parameters}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{14--15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.14},
  URN =		{urn:nbn:de:0030-drops-36612},
  doi =		{10.4230/LIPIcs.CSL.2012.14},
  annote =	{Keywords: Model theory, finite model theory, graph invariants}
}
Document
DOI: 10.4230/LIPIcs.CSL.2012.411
Connection Matrices and the Definability of Graph Parameters

Authors: Tomer Kotek and Johann A. Makowsky

Published in: LIPIcs, Volume 16, Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL (2012)

Abstract
In this paper we extend the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with modular counting CMSOL of B. Godlin, T. Kotek and J.A. Makowsky (2008 and 2009), and demonstrate its vast applicability in simplifying known and new non-definability results of graph properties and finding new non-definability results for graph parameters. We also prove a Feferman-Vaught Theorem for the logic CFOL, First Order Logic with the modular counting quantifiers.
Cite as

Tomer Kotek and Johann A. Makowsky. Connection Matrices and the Definability of Graph Parameters. In Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 16, pp. 411-425, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kotek_et_al:LIPIcs.CSL.2012.411,
  author =	{Kotek, Tomer and Makowsky, Johann A.},
  title =	{{Connection Matrices and the Definability of Graph Parameters}},
  booktitle =	{Computer Science Logic (CSL'12) - 26th International Workshop/21st Annual Conference of the EACSL},
  pages =	{411--425},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-42-2},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{16},
  editor =	{C\'{e}gielski, Patrick and Durand, Arnaud},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2012.411},
  URN =		{urn:nbn:de:0030-drops-36871},
  doi =		{10.4230/LIPIcs.CSL.2012.411},
  annote =	{Keywords: Model theory, finite model theory, graph invariants}
}
Document
DOI: 10.4230/LIPIcs.CSL.2011.553
Model Theory in Computer Science: My Own Recurrent Themes

Authors: Johann A. Makowsky

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract
I review my own experiences in research and the management of science.
Cite as

Johann A. Makowsky. Model Theory in Computer Science: My Own Recurrent Themes. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 553-567, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{makowsky:LIPIcs.CSL.2011.553,
  author =	{Makowsky, Johann A.},
  title =	{{Model Theory in Computer Science: My Own Recurrent Themes}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{553--567},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.553},
  URN =		{urn:nbn:de:0030-drops-32567},
  doi =		{10.4230/LIPIcs.CSL.2011.553},
  annote =	{Keywords: model theory, finite model theory, databases, graph invariants}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact