3 citations · 9 across the 10 of their papers we have counts for
11 papers
Property Testing for Recursive Query Languages
Isolde Adler, Carsten Lutz, Quentin Manière +2
In the context of database querying, property testing provides a framework for testing query answers with high confidence while inspecting only a sublinear part of the database, th…
Partially Finite Model Reasoning in Description Logics Extended Version
Tomasz Gogacz, Filip Murlak, Marcin Przybyłko +2
Aiming to harmonise finite and infinite model reasoning, we initiate the study of partially finite models, where the reasoning task comes with a formula that specifies a part of th…
Let's Play Tag: Linear Time Evaluation of Conjunctive Queries under TGD Constraints
Nofar Carmeli, Carsten Lutz, Marcin Przybyłko
We study the limits of linear time evaluation of conjunctive queries under constraints expressed as tuple-generating dependencies (TGDs), across several modes of query evaluation:…
Spectra of Cardinality Queries over Description Logic Knowledge Bases
Quentin Manière, Marcin Przybyłko
Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or…
Computing measures of weak-MSO definable sets of trees
Damian Niwiński, Marcin Przybyłko, Michał Skrzypczak
This work addresses the problem of computing measures of recognisable sets of infinite trees. An algorithm is provided to compute the probability measure of a tree language recogni…
Efficient Answer Enumeration in Description Logics with Functional Roles -- Extended Version
Carsten Lutz, Marcin Przybylko
We study the enumeration of answers to ontology-mediated queries when the ontology is formulated in a description logic that supports functional roles and the query is a CQ. In par…
Efficiently Enumerating Answers to Ontology-Mediated Queries
Carsten Lutz, Marcin Przybyłko
We study the enumeration of answers to ontology-mediated queries (OMQs) where the ontology is a set of guarded TGDs or formulated in the description logic ELI and the query is a co…
Answer Counting under Guarded TGDs
Cristina Feier, Carsten Lutz, Marcin Przybyłko
We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query…
The Uniform Measure of Simple Regular Sets of Infinite Trees
Marcin Przybyłko, Michał Skrzypczak
We consider the problem of computing the measure of a regular set of infinite binary trees. While the general case remains unsolved, we show that the measure of a language can be c…
On Computing the Measures of First-Order Definable Sets of Trees
Marcin Przybyłko
We consider the problem of computing the measure of a regular language of infinite binary trees. While the general case remains unsolved, we show that the measure of a language def…
Tree games with regular objectives
Marcin Przybyłko
We study tree games developed recently by Matteo Mio as a game interpretation of the probabilistic -calculus. With expressive power comes complexity. Mio showed that tree games…