Zobrazeno 1 - 10
of 152
pro vyhledávání: '"SCHWEIKARDT, NICOLE"'
In the logical framework introduced by Grohe and Tur\'an (TOCS 2004) for Boolean classification problems, the instances to classify are tuples from a logical structure, and Boolean classifiers are described by parametric models based on logical formu
Externí odkaz:
http://arxiv.org/abs/2411.04003
Autor:
Scheidt, Benjamin, Schweikardt, Nicole
Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is mainly used as an imperfect way to test for isomorphism, the algorithm permeat
Externí odkaz:
http://arxiv.org/abs/2407.16022
We present an index structure, called the color-index, to boost the evaluation of acyclic conjunctive queries (ACQs) over binary schemas. The color-index is based on the color refinement algorithm, a widely used subroutine for graph isomorphism testi
Externí odkaz:
http://arxiv.org/abs/2405.12358
We present a theoretical framework for the extraction and transformation of text documents. We propose to use a two-phase process where the first phase extracts span-tuples from a document, and the second phase maps the content of the span-tuples int
Externí odkaz:
http://arxiv.org/abs/2405.12350
Autor:
Scheidt, Benjamin, Schweikardt, Nicole
We introduce the 2-sorted counting logic $GC^k$ that expresses properties of hypergraphs. This logic has available k variables to address hyperedges, an unbounded number of variables to address vertices, and atomic formulas E(e,v) to express that a v
Externí odkaz:
http://arxiv.org/abs/2303.10980
Autor:
Schmid, Markus L., Schweikardt, Nicole
We consider the problem of evaluating regular spanners over compressed documents, i.e., we wish to solve evaluation tasks directly on the compressed data, without decompression. As compressed forms of the documents we use straight-line programs (SLPs
Externí odkaz:
http://arxiv.org/abs/2101.10890
Autor:
Schmid, Markus L., Schweikardt, Nicole
Publikováno v:
Logical Methods in Computer Science, Volume 20, Issue 4 (November 21, 2024) lmcs:8614
The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS
Externí odkaz:
http://arxiv.org/abs/2010.13442
Publikováno v:
Logical Methods in Computer Science, Volume 18, Issue 2 (May 10, 2022) lmcs:6858
A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree
Externí odkaz:
http://arxiv.org/abs/2010.08382
We consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of first-order logic that allows to aggreg
Externí odkaz:
http://arxiv.org/abs/2009.10574
Publikováno v:
Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, pp. 58:1-58:15, 2019
Marx (STOC~2010, J.~ACM 2013) introduced the notion of submodular width of a conjunctive query (CQ) and showed that for any class $\Phi$ of Boolean CQs of bounded submodular width, the model-checking problem for $\Phi$ on the class of all finite stru
Externí odkaz:
http://arxiv.org/abs/2003.01075