12 citations · 34 across the 17 of their papers we have counts for
19 papers
On the Tutte and matching polynomials for complete graphs
Tomer Kotek, Johann A. Makowsky
Let be the Tutte polynomial for graphs. We study the sequence where are non-negative integers, and show that for every the sequ…
Pebble-Intervals Automata and FO2 with Two Orders (Extended Version)
Nadia Labai, Tomer Kotek, Magdalena Ortiz +1
We introduce a novel automata model, called pebble-intervals automata (PIA), and study its power and closure properties. PIAs are tailored for a decidable fragment of FO that is im…
The exact complexity of the Tutte polynomial
Tomer Kotek, Johann A. Makowsky
This is a survey on the exact complexity of computing the Tutte polynomial. It is the longer 2017 version of Chapter 25 of the CRC Handbook on the Tutte polynomial and related topi…
On sequences of polynomials arising from graph invariants
T. Kotek, J. A. Makowsky, E. V. Ravve
Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebrai…
A logician's view of graph polynomials
J. A. Makowsky, E. V. Ravve, T. Kotek
Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polyno…
On the complexity of generalized chromatic polynomials
A. Goodall, M. Hermann, T. Kotek +2
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for h…
On the automated verification of web applications with embedded SQL
Shachar Itzhaky, Tomer Kotek, Noam Rinetzky +4
A large number of web applications is based on a relational database together with a program, typically a script, that enables the user to interact with the database through embedd…
Efficient computation of generalized Ising polynomials on graphs with fixed clique-width
Tomer Kotek, Johann A. Makowsky
Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to clique-width. In contrast…
Monadic second order finite satisfiability and unbounded tree-width
Tomer Kotek, Helmut Veith, Florian Zuleger
The finite satisfiability problem of monadic second order logic is decidable only on classes of structures of bounded tree-width by the classic result of Seese (1991). We prove the…
Extending ALCQIO with reachability
Tomer Kotek, Mantas Simkus, Helmut Veith +1
We introduce a description logic ALCQIO_{b,Re} which adds reachability assertions to ALCQIO, a sub-logic of the two-variable fragment of first order logic with counting quantifiers…
Shape and Content: Incorporating Domain Knowledge into Shape Analysis
Diego Calvanese, Tomer Kotek, Mantas Šimkus +2
The verification community has studied dynamic data structures primarily in a bottom-up way by analyzing pointers and the shapes induced by them. Recent work in fields such as sepa…
Recurrence Relations for Graph Polynomials on Bi-iterative Families of Graphs
Tomer Kotek, Johann A. Makowsky
We show that any graph polynomial from a wide class of graph polynomials yields a recurrence relation on an infinite class of families of graphs. The recurrence relations we obtain…
Connection Matrices and the Definability of Graph Parameters
Tomer Kotek, Johann A. Makowsky
In this paper we extend and prove in detail the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with counting (CMSOL) from B…
Domination Polynomials of Graph Products
Tomer Kotek, James Preen, Peter Tittmann
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of t…
Subset-Sum Representations of Domination Polynomials
Tomer Kotek, James Preen, Peter Tittmann
The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this p…
Recurrence relations and splitting formulas for the domination polynomial
Tomer Kotek, James Preen, Frank Simon +2
The domination polynomial D(G,x) of a graph G is the generating function of its dominating sets. We prove that D(G,x) satisfies a wide range of reduction formulas. We show linear r…
Complexity of Ising Polynomials
Tomer Kotek
This paper deals with the partition function of the Ising model from statistical mechanics, which is used to study phase transitions in physical systems. A special case of interest…
Definability of Combinatorial Functions and Their Linear Recurrence Relations
T. Kotek, J. A. Makowsky
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, Be…
On the Reconstruction of Graph Invariants
T. Kotek
The reconstruction conjecture has remained open for simple undirected graphs since it was suggested in 1941 by Kelly and Ulam. In an attempt to prove the conjecture, many graph inv…