Zobrazeno 1 - 10
of 57
pro vyhledávání: '"Kotek, Tomer"'
Autor:
Kotek, Tomer, Makowsky, Johann A.
Publikováno v:
Fundamenta Informaticae, Volume 186, Issues 1-4: Trakhtenbrot's centenary (October 21, 2022) fi:8839
Let $T(G;X,Y)$ be the Tutte polynomial for graphs. We study the sequence $t_{a,b}(n) = T(K_n;a,b)$ where $a,b$ are non-negative integers, and show that for every $\mu \in \N$ the sequence $t_{a,b}(n)$ is ultimately periodic modulo $\mu$ provided $a \
Externí odkaz:
http://arxiv.org/abs/2112.06581
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 important for reasoning about structures that use data values from infin
Externí odkaz:
http://arxiv.org/abs/1912.00171
Autor:
Kotek, Tomer, Makowsky, Johann A.
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 topics, edited by J. Ellis-Monaghan and I. Moffatt, which is due to appear
Externí odkaz:
http://arxiv.org/abs/1910.08915
Autor:
Itzhaky, Shachar, Kotek, Tomer, Rinetzky, Noam, Sagiv, Mooly, Tamir, Orr, Veith, Helmut, Zuleger, Florian
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 embedded SQL queries and commands. In this paper, we introduce a method for
Externí odkaz:
http://arxiv.org/abs/1610.02101
Autor:
Kotek, Tomer, Makowsky, Johann A.
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, graph polynomials which are definable in MSOL on the vocabulary of h
Externí odkaz:
http://arxiv.org/abs/1505.06617
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 following problem is decidable: Input: (i) A monadic second order log
Externí odkaz:
http://arxiv.org/abs/1505.06622
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. ALCQIO_{b,Re} is well-suited for applications in software verificati
Externí odkaz:
http://arxiv.org/abs/1402.6804
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 separation logic has made significant progress in extracting shapes from p
Externí odkaz:
http://arxiv.org/abs/1312.6624
Autor:
Kotek, Tomer, Makowsky, Johann A.
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 have coefficients which themselves satisfy linear recurrence relation
Externí odkaz:
http://arxiv.org/abs/1309.4020
Autor:
Kotek, Tomer, Makowsky, Johann A.
Publikováno v:
Logical Methods in Computer Science, Volume 10, Issue 4 (October 31, 2014) lmcs:731
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. Godlin, T. Kotek and J.A. Makowsky (2008) and J.A. Makowsky (2009).
Externí odkaz:
http://arxiv.org/abs/1308.3654