Author name cluster

Filip Murlak

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.

13 papers

2 author rows

AAAI Conference 2026 Conference Paper

Revisiting Conjunctive Query Entailment for S

Yazmín Ibáñez-García
Jean Christoph Jung
Vincent Michielini
Filip Murlak

We clarify the complexity of answering unions of conjunctive queries over knowledge bases formulated in the description logic S, the extension of ALC with transitive roles. Contrary to what existing partial results suggested, we show that the problem is, in fact, 2ExpTime-complete; hardness already holds in the presence of two transitive roles and for Boolean conjunctive queries. We complement this result by showing that the problem remains in coNExpTime when the input query is rooted or is restricted to use at most one transitive role (but may use arbitrarily many non-transitive roles).

PDF Details DOI

MFCS Conference 2025 Conference Paper

On Graph Queries and Modal Constraints (Invited Talk)

Filip Murlak

Some fundamental problems in database theory and knowledge representation can be viewed as instances of the query entailment problem. While query evaluation asks whether a given query holds in a specific structure, query entailment consists in determining whether the query holds in every model of a given theory that extends that structure. The input structure represents the raw data stored in a database; the theory captures contextual information such as a set of database constraints or an ontology; and the query is used to extract specific information of interest. The recent proliferation of graph databases has brought the database and knowledge representation communities closer together, as many key problems in both fields involve the same structures - labelled graphs - and similar combinations of formalisms for theories and queries. A notable example is the combination of description logics and conjunctive regular path queries. Description logics are a family of formalisms based on fragments of first order logic, akin to modal logics. They are among the most prominent ontology languages and they are capable of expressing most kinds of constraints relevant in graph databases. Conjunctive regular path queries extend conjunctive queries (primitive positive first-order formulas) by allowing regular expressions over binary predicates to be used as atoms. They form the core of practical query languages employed in graph database systems and the Semantic Web. What distinguishes the two fields is the approach to infinity: knowledge representation embraces infinite models, whereas database theory focuses on finite models. Although many cases of the entailment problem have long been solved over unrestricted (finite or infinite) models, their finite-model counterparts have only recently seen progress, and many questions remain open.

Details

AIJ Journal 2023 Journal Article

Answering regular path queries mediated by unrestricted SQ ontologies

Víctor Gutiérrez-Basulto
Yazmín Ibáñez-García
Jean Christoph Jung
Filip Murlak

A prime application of description logics is ontology-mediated query answering, with the query language often reaching far beyond instance queries. Here, we investigate this task for positive existential two-way regular path queries and ontologies formulated in the expressive description logic SQ u, where SQ u denotes the extension of the basic description logic ALC with transitive roles ( S ) and qualified number restrictions ( Q ) which can be unrestrictedly applied to both non-transitive and transitive roles ( ⋅ u ). Notably, the latter is usually forbidden in expressive description logics. As the main contribution, we show decidability of ontology-mediated query answering in that setting and establish tight complexity bounds, namely 2ExpTime-completeness in combined complexity and coNP-completeness in data complexity. Since the lower bounds are inherited from the fragment ALC, we concentrate on providing upper bounds. As main technical tools we establish a tree-like countermodel property and a characterization of when a query is not satisfied in a tree-like interpretation. Together, these results allow us to use an automata-based approach to query answering.

Details DOI

IJCAI Conference 2023 Conference Paper

Finite Entailment of UCRPQs over ALC Ontologies (Extended Abstract)

Víctor Gutiérrez-Basulto
Albert Gutowski
Yazmín Ibáñez-García
Filip Murlak

PDF Details DOI

KR Conference 2022 Conference Paper

Finite Entailment of UCRPQs over ALC Ontologies

Víctor Gutiérrez-Basulto
Albert Gutowski
Yazmín Ibáñez-García
Filip Murlak

We investigate the problem of finite entailment of ontology-mediated queries. We consider the expressive query language, unions of conjunctive regular path queries (UCRPQs), extending the well-known class of union of conjunctive queries, with regular expressions over roles. We look at ontologies formulated using the description logic ALC, and show a tight 2ExpTime upper bound for entailment of UCRPQs. At the core of our decision procedure, there is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input UCRPQ.

PDF Details DOI

KR Conference 2020 Conference Paper

On Finite Entailment of Non-Local Queries in Description Logics

Tomasz Gogacz
Víctor Gutiérrez-Basulto
Albert Gutowski
Yazmín Ibáñez-García
Filip Murlak

We study the problem of finite entailment of ontology-mediated queries. Going beyond local queries, we allow transitive closure over roles. We focus on ontologies formulated in the description logics ALCOI and ALCOQ, extended with transitive closure. For both logics, we show 2EXPTIME upper bounds for finite entailment of unions of conjunctive queries with transitive closure. We also provide a matching lower bound by showing that finite entailment of conjunctive queries with transitive closure in ALC is 2EXPTIME-hard

PDF Details DOI

ECAI Conference 2020 Conference Paper

Ontology Focusing: Knowledge-Enriched Databases on Demand

Tomasz Gogacz
Víctor Gutiérrez-Basulto
Yazmín Ibáñez-García
Filip Murlak
Magdalena Ortiz 0001
Mantas Simkus

We propose a novel use of ontologies to aid the on-demand design of data-centric systems. By means of a process that we call focusing, a schema for a (possibly knowledge-enriched) database can be obtained semi-automatically from an existing ontology and a specification of the scope of the desired system. We formalize the inputs and outputs of focusing, and identify relevant computational problems: finding a schema via focusing, testing its consistency, and answering queries in the knowledge-enriched databases it produces. These definitions are independent from the ontology language. We then study focusing for selected description logics as ontology languages, and popular classes of queries for specifying the scope of the system. For several representative combinations, we study the decidability and complexity of the identified computational problems. As a by-product, we isolate (and solve) mixed variants of the classical satisfiability and entailment problems, where selected predicates are required to have finite extension, as well as the nullability problem, which is closely related to query emptiness.

Details

IJCAI Conference 2019 Conference Paper

On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles

Tomasz Gogacz
Víctor Gutiérrez-Basulto
Yazmín Ibáñez-García
Jean Christoph Jung
Filip Murlak

We study the description logic SQ with number restrictions applicable to transitive roles, extended with either nominals or inverse roles. We show tight 2EXPTIME upper bounds for unrestricted entailment of regular path queries for both extensions and finite entailment of positive existential queries for nominals. For inverses, we establish 2EXPTIME-completeness for unrestricted and finite entailment of instance queries (the latter under restriction to a single, transitive role).

PDF Details

KR Conference 2018 Conference Paper

Finite Query Answering in expressive Description Logics with transitive Roles

Tomasz Gogacz
Yazmin Ibanez-Garcia
Filip Murlak

We study the problem of finite ontology mediated query answering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA is relevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automatabased decision procedures with optimal complexity bounds.

Highlights Conference 2013 Conference Abstract

Game or not Game?

Alessandro Facchini
Michał Skrzypczak
Filip Murlak

Recently the present authors have shown that both the non-deterministic and the alternating Rabin-Mostowski index problems are decidable for languages recognisable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. In order to be able to claim decidability of the index problem for a given subclass of regular languages, one should however prove that membership in is decidable too. In this talk we show that membership in the class of languages recognizable by game automata is decidable.

PDF Details

MFCS Conference 2012 Conference Paper

Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?

Filip Murlak
Michal Oginski
Marcin Przybylko

Abstract In static analysis of queries over trees in the presence of schemas, there is an exponential complexity gap between conjunctive queries (CQs, positive existential first-order formulae without disjunction) and tree patterns (tree-like acyclic CQs). Motivated by applications in XML data management, we consider various restrictions of CQs that bring their complexity down to that of tree patterns. Most importantly, we show that vertical tree patterns can be costlessly extended with full horizontal CQs over children. We also consider restricted classes of schemas and show that under disjunction-free schemas the complexity of static analysis sometimes drops dramatically.

Details

CSL Conference 2009 Conference Paper

Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata

Jacques Duparc
Alessandro Facchini
Filip Murlak

Abstract For deterministic tree automata, classical hierarchies, like Mostowski-Rabin (or index) hierarchy, Borel hierarchy, or Wadge hierarchy, are known to be decidable. However, when it comes to non-deterministic tree automata, none of these hierarchies is even close to be understood. Here we make an attempt in paving the way towards a clear understanding of tree automata. We concentrate on the class of linear game automata (LGA), and prove within this new context, that all corresponding hierarchies mentioned above—Mostowski-Rabin, Borel, and Wadge—are decidable. The class LGA is obtained by taking linear tree automata with alternation restricted to the choice of path in the input tree. Despite their simplicity, LGA recognize sets of arbitrary high Borel rank. The actual richness of LGA is revealed by the height of their Wadge hierarchy: ( ω ω ) ω.

Details

CSL Conference 2005 Conference Paper

On Deciding Topological Classes of Deterministic Tree Languages

Filip Murlak

Abstract It has been proved by Niwiński and Walukiewicz that a deterministic tree language is either Π \(_{\rm 1}^{\rm 1}\) -complete or it is on the level Π \(_{\rm 3}^{\rm 0}\) of the Borel hierarchy, and that it can be decided effectively which of the two takes place. In this paper we show how to decide if the language recognized by a given deterministic tree automaton is on the Π \(_{\rm 2}^{\rm 0}\), the Σ \(^{\rm 0}_{\rm 2}\), or the Σ \(^{\rm 0}_{\rm 3}\) level. Together with the previous results it gives a procedure calculating the exact position of a deterministic tree language in the topological hierarchy.

Details