Source author record

Marcin Przybyłko

Marcin Przybyłko appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Computer Science and Game Theory Databases Logic in Computer Science

Catalog footprint

What is connected

3works

4topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Efficiently Enumerating Answers to Ontology-Mediated Queries

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 conjunctive query (CQ). In addition to the traditional notion of an answer, we propose and study two novel notions of partial answers that can take into account nulls generated by existential quantifiers in the ontology. Our main result is that enumeration of the traditional complete answers and of both kinds of partial answers is possible with linear-time preprocessing and constant delay for OMQs that are both acyclic and free-connex acyclic. We also provide partially matching lower bounds. Similar results are obtained for the related problems of testing a single answer in linear time and of testing multiple answers in constant time after linear time preprocessing. In both cases, the border between tractability and intractability is characterized by similar, but slightly different acyclicity properties.

preprint2020arXiv

The Uniform Measure of Simple Regular Sets of Infinite Trees

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.

preprint2014arXiv

Tree games with regular objectives

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.