Author name cluster

Marcin Przybyłko

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

AAAI Conference 2025 Conference Paper

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 infinity, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over ALCIF ontologies: they are essentially the subsets of N and infinity closed under addition. For most sublogics of ALCIF, we show that possible spectra enjoy simpler shapes, being [ m, infinity ] or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of ALCIF. We also study the data complexity of computing the proposed effective representation and establish the FP^NP[log]-completeness of this task under several settings.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Efficient Answer Enumeration in Description Logics with Functional Roles

Carsten Lutz
Marcin Przybyłko

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 particular, we show that enumeration is possible with linear preprocessing and constant delay when a certain extension of the CQ (pertaining to functional roles) is acyclic and free-connex acyclic. This holds both for complete answers and for partial answers. We provide matching lower bounds for the case where the query is self-join free.

PDF Details DOI

Highlights Conference 2021 Conference Abstract

Answer Counting under Guarded TGDs

Marcin Przybyłko

Tuple-generating dependencies (TGDs) are a prominent formalism for formulating database constraints. A TGD states that if certain facts are true, then certain other facts must be true as well. This can be interpreted in different ways. In ontology-mediated querying, TGDs give rise to ontology languages and are used to derive new facts in addition to those that are present in the database. In a more classical setup that we refer to as querying under constraints, TGDs are used as integrity constraints on the database, that is, a TGD expresses the promise that if certain facts are present in the database, then certain other facts are present as well. In this talk, I will discuss the problem of counting answers to ontology-mediated queries (OMQs) in the context of parameterized complexity theory, with the query being the parameter. I will focus on the case where the ontology is given as a set of guarded TGDs while the actual queries are (unions of) conjunctive queries ((U)CQs)and show how to, in this setting, lift a recent classification due to Dell et al. for UCQs without ontologies and constraints to the world of OMQs. This presentation is based on a joint work with Cristina Feier and Carsten Lutz, published at ICDT 2021.

Details

I&C Journal 2021 Journal Article

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 computed when the set is given in one of the following three formalisms: a first-order formula with no descendant relation; a Boolean combination of conjunctive queries (with descendant relation); or by a non-deterministic safety tree automaton. Additionally, in the first two cases the measure of the set is always rational, while in the third it is an algebraic number. Moreover, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational (but algebraic) measure.

Details DOI

GandALF Workshop 2018 Workshop Paper

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 defined by a first-order formula with no descendant relation or by a Boolean combination of conjunctive queries (with descendant relation) is rational and computable. Additionally, we provide an example of a first-order formula that uses descendant relation and defines a language of infinite trees having an irrational measure.

PDF Details DOI

Highlights Conference 2018 Conference Abstract

On Computing the Measures of First-Order Definable Sets of Trees

Marcin Przybyłko

ABSTRACT. 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 defined by a first-order formula with no descendant relation or by a Boolean combination of conjunctive queries (with descendant relation) is rational and computable. Additionally, we provide an example of a first-order formula that uses descendant relation and defines a language having an irrational measure.

Details

Highlights Conference 2014 Conference Abstract

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. It was shown that tree games are able to encode the Blackwell games and, consequently, are not determined under deterministic strategies. First, we will show that tree games with objectives recognisable by so-called game automata are determined under deterministic, finite memory strategies. Then, for the case of arbitrary regular languages of trees, we will present an exponential time algorithm for deciding the determinacy of a finite tree game under deterministic strategies.

PDF Details

GandALF Workshop 2014 Workshop Paper

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 are able to encode Blackwell games and, consequently, are not determined under deterministic strategies. We show that non-stochastic tree games with objectives recognisable by so-called game automata are determined under deterministic, finite memory strategies. Moreover, we give an elementary algorithmic procedure which, for an arbitrary regular language L and a finite non-stochastic tree game with a winning objective L decides if the game is determined under deterministic strategies.

PDF Details DOI