Author name cluster

Michael Benedikt

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.

22 papers

2 author rows

CSL Conference 2026 Conference Paper

Analysis of Logics with Arithmetic

Michael Benedikt
Chia-Hsuan Lu
Tony Tan

We present new results on finite satisfiability of logics with counting and arithmetic. One result is a tight bound on the complexity of satisfiability of logics with so-called local Presburger quantifiers, which sum over neighbors of a node in a graph. A second contribution concerns computing a semilinear representation of the cardinalities associated with a formula in two variable logic extended with counting quantifiers. Such a representation allows you to get bounds not only on satisfiability for these logics, but for satisfiability in the presence of additional "global cardinality constraints": restrictions on cardinalities of unary formulas, expressed using arbitrary decidability logics over arithmetic. In the process, we provide simpler proofs of some key prior results on finite satisfiability and semi-linearity of the spectrum for these logics.

Details

NeurIPS Conference 2024 Conference Paper

Almost Surely Asymptotically Constant Graph Neural Networks

Sam Adam-Day
Michael Benedikt
İsmail İ. Ceylan
Ben Finkelshtein

We present a new angle on the expressive power of graph neural networks (GNNs) by studying how the predictions of real-valued GNN classifiers, such as those classifying graphs probabilistically, evolve as we apply them on larger graphs drawn from some random graph model. We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models, with aggregates including mean and the attention-based mechanism of graph transformers. Our results apply to a broad class of random graph models, including sparse and dense variants of the Erdős-Rényi model, the stochastic block model, and the Barabási-Albert model. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.

PDF Details DOI

KR Conference 2024 Conference Paper

Monotone Rewritability and the Analysis of Queries, Views, and Rules

Michael Benedikt
Stanislav Kikot
Johannes Marti
Piotr Ostropolski-Nawelaja

We study the interaction of views, queries, and background knowledge in the form of existential rules. The motivating questions concern monotonic determinacy of a query using views w. r. t. rules, which refers to the ability to recover the query answer from the views via a monotone function. We study the decidability of monotonic determinacy, and compare with variations that require the “recovery function” to be in a well-known monotone query language, such as conjunctive queries or Datalog. Surprisingly, we find that even in the presence of basic existential rules, the borderline between well-behaved and badly-behaved answerability differs radically from the unconstrained case. In order to understand this boundary, we require new results concerning entailment problems involving views and rules.

PDF Details DOI

JMLR Journal 2024 Journal Article

Towards Unbiased Exploration in Partial Label Learning

Zsolt Zombori
Agapi Rissaki
Kristóf Szabó
Wolfgang Gatterbauer
Michael Benedikt

We consider learning a probabilistic classifier from partially-labelled supervision (inputs denoted with multiple possibilities) using standard neural architectures with a softmax as the final layer. We identify a bias phenomenon that can arise from the softmax layer in even simple architectures that prevents proper exploration of alternative options, making the dynamics of gradient descent overly sensitive to initialization. We introduce a novel loss function that allows for unbiased exploration within the space of alternative outputs. We give a theoretical justification for our loss function, and provide an extensive evaluation of its impact on synthetic data, on standard partially labelled benchmarks and on a contributed novel benchmark related to an existing rule learning challenge. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2024. ( edit, beta )

PDF Details

KR Conference 2020 Conference Paper

Balancing Expressiveness and Inexpressiveness in View Design

Michael Benedikt
Pierre Bourhis
Louis Jachiet
Efthymia Tsamoura

We study the design of data publishing mechanisms that allow a collection of autonomous distributed datasources to collaborate to support queries. A common mechanism for data publishing is via views: functions that expose derived data to users, usually specified as declarative queries. Our autonomy assumption is that the views must be on individual sources, but with the intention of supporting integrated queries. In deciding what data to expose to users, two considerations must be balanced. The views must be sufficiently expressive to support queries that users want to ask -- the utility of the publishing mechanism. But there may also be some expressiveness restriction. Here we consider two restrictions, a minimal information requirement, saying that the views should reveal as little as possible while supporting the utility query, and a non-disclosure requirement, formalizing the need to prevent external users from computing information that data owners do not want revealed. We investigate the problem of designing views that satisfy both an expressiveness and an inexpressiveness requirement, for views in a restricted declarative language (conjunctive queries), and for arbitrary views.

PDF Details DOI

Highlights Conference 2020 Conference Abstract

Nested Data, Interpolation, and Synthesis

Michael Benedikt

This talk will be about nested sets — basically, finite levels of the cumulative hierarchy in set theory. The first part of the presentation will review some languages proposed for defining transformations on nested sets from a few decades ago. The next part will go into some connections of these languages with interpretations, interpolation, and intuitionistic logic, based on joint work with Pierre Pradic.

Details

IJCAI Conference 2019 Conference Paper

Reasoning about Disclosure in Data Integration in the Presence of Source Constraints

Michael Benedikt
Pierre Bourhis
Louis Jachiet
Michaël Thomazo

Data integration systems allow users to access data sitting in multiple sources by means of queries over a global schema, related to the sources via mappings. Datasources often contain sensitive information, and thus an analysis is needed to verify that a schema satisfies a privacy policy, given as a set of queries whose answers should not be accessible to users. Such an analysis should take into account not only knowledge that an attacker may have about the mappings, but also what they may know about the semantics of the sources. In this paper, we show that source constraints can have a dramatic impact on disclosure analysis. We study the problem of determining whether a given data integration system discloses a source query to an attacker in the presence of constraints, providing both lower and upper bounds on source-aware disclosure analysis.

PDF Details

AAAI Conference 2018 Conference Paper

Goal-Driven Query Answering for Existential Rules With Equality

Michael Benedikt
Boris Motik
Efthymia Tsamoura

Inspired by the magic sets for Datalog, we present a novel goal-driven approach for answering queries over terminating existential rules with equality (aka TGDs and EGDs). Our technique improves the performance of query answering by pruning the consequences that are not relevant for the query. This is challenging in our setting because equalities can potentially affect all predicates in a dataset. We address this problem by combining the existing singularization technique with two new ingredients: an algorithm for identifying the rules relevant to a query and a new magic sets algorithm. We show empirically that our technique can signiﬁcantly improve the performance of query answering, and that it can mean the difference between answering a query in a few seconds or not being able to process the query at all.

PDF Details

AIJ Journal 2018 Journal Article

Logical foundations of information disclosure in ontology-based data integration

Michael Benedikt
Bernardo Cuenca Grau
Egor V. Kostylev

Ontology-based data integration systems allow users to effectively access data sitting in multiple sources by means of queries over a global schema described by an ontology. In practice, data sources often contain sensitive information that the data owners want to keep inaccessible to users. Our aim in this paper is to lay the logical foundations of information disclosure in ontology-based data integration. Our focus is on the semantic requirements that a data integration system should satisfy before it is made available to users for querying, as well as on the computational complexity of checking whether such requirements are fulfilled. In particular, we formalise and study the problem of determining whether a given data integration system discloses a source query to an attacker. We consider disclosure on a particular dataset, and also whether a schema admits a dataset on which disclosure occurs. We provide matching lower and upper complexity bounds on disclosure analysis, in the process introducing a number of techniques for analysing logical privacy issues in ontology-based data integration.

Details DOI

JAIR Journal 2018 Journal Article

Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli
Michael Benedikt
Pierre Bourhis
Michael Vanden Boom

We consider entailment problems involving powerful constraint languages such as frontier-guarded existential rules in which we impose additional semantic restrictions on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural variants of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in these conditions lead to undecidability.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

Reformulating Queries: Theory and Practice

Michael Benedikt
Egor V. Kostylev
Fabio Mogavero
Efthymia Tsamoura

We consider a setting where a user wants to pose a query against a dataset where background knowledge, expressed as logical sentences, is available, but only a subset of the information can be used to answer the query. We thus want to reformulate the user query against the subvocabulary, arriving at a query equivalent to the user’s query assuming the background theory, but using only the restricted vocabulary. We consider two variations of the problem, one where we want any such reformulation and another where we restrict the size. We present a classification of the complexity of the problem, then provide algorithms for solving the problems in practice and evaluate their performance.

PDF Details

AAAI Conference 2017 Conference Paper

Source Information Disclosure in Ontology-Based Data Integration

Michael Benedikt
Bernardo Cuenca Grau
Egor Kostylev

PDF Details

IJCAI Conference 2016 Conference Paper

Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli
Michael Benedikt
Pierre Bourhis
Michael Vanden Boom

We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.

PDF Details

IJCAI Conference 2015 Conference Paper

Combining Existential Rules and Description Logics

Antoine Amarilli
Michael Benedikt

Query answering under existential rules — implications with existential quantifiers in the head — is known to be decidable when imposing restrictions on the rule bodies such as frontier-guardedness [Baget et al. , 2010; 2011a]. Query answering is also decidable for description logics [Baader, 2003], which further allow disjunction and functionality constraints (assert that certain relations are functions); however, they are focused on ER-type schemas, where relations have arity two. This work investigates how to get the best of both worlds: having decidable existential rules on arbitrary arity relations, while allowing rich description logics, including functionality constraints, on arity-two relations. We first show negative results on combining such decidable languages. Second, we introduce an expressive set of existential rules (frontier-one rules with a certain restriction) which can be combined with powerful constraints on aritytwo relations (e. g. GC2, ALCQIb) while retaining decidable query answering. Further, we provide conditions to add functionality constraints on the higher-arity relations.

PDF Details

TCS Journal 2014 Journal Article

The per-character cost of repairing word languages

Michael Benedikt
Gabriele Puppis
Cristian Riveros

We show how to calculate the maximum number of edits per character needed to convert any string in one regular language to a string in another language. Our algorithm makes use of a local determinization procedure applicable to a subclass of distance automata. We then show how to calculate the same property when the editing needs to be done in streaming fashion, by a finite state transducer, using a reduction to mean-payoff games. In this case, we show that the optimal streaming editor can be produced in P.

Details DOI

Highlights Conference 2013 Conference Abstract

Bisimilarity of pushdown automata is nonelementary

Michael Benedikt
Stefan Göller
Stefan Kiefer
Andrzej Murawski

Given two pushdown systems, the bisimilarity problem asks whether they are bisimilar. While this problem is known to be decidable our main result states that it is nonelementary, improving EXPTIME-hardness, which was the previously best known lower bound for this problem. Our lower bound result holds for normed pushdown systems as well.

PDF Details

MFCS Conference 2013 Conference Paper

Determinacy and Rewriting of Top-Down and MSO Tree Transformations

Michael Benedikt
Joost Engelfriet
Sebastian Maneth

Abstract A query is determined by a view, if the result to the query can be reconstructed from the result of the view. We consider the problem of deciding for two given tree transformations, whether one is determined by the other. If the view transformation is induced by a tree transducer that may copy, then determinacy is undecidable, even for identity queries. For a large class of non-copying views, namely compositions of functional extended linear top-down tree transducers with regular look-ahead, we show that determinacy is decidable, where queries are given by deterministic top-down tree transducers with regular look-ahead or by MSO tree transducers. We also show that if a query is determined, then it can be rewritten into a query that works directly over the view and is in the same class as the given query. The proof relies on the decidability of equivalence for the two considered classes of queries, and on their closure under composition.

Details

MFCS Conference 2013 Conference Paper

Rewriting Guarded Negation Queries

Vince Bárány
Michael Benedikt
Balder ten Cate

Abstract The Guarded Negation Fragment (GNFO) is a fragment of first-order logic that contains all unions of conjunctive queries, a restricted form of negation that suffices for expressing some common uses of negation in SQL queries, and a large class of integrity constraints. At the same time, as was recently shown, the syntax of GNFO is restrictive enough so that static analysis problems such as query containment are still decidable. This suggests that, in spite of its expressive power, GNFO queries are amenable to novel optimizations. In this paper we provide further evidence for this, establishing that GNFO queries have distinctive features with respect to rewriting. Our results include effective preservation theorems for GNFO, Craig Interpolation and Beth Definability results, and the ability to express the certain answers of queries with respect to GNFO constraints within very restricted logics.

Details

CSL Conference 2010 Conference Paper

Automata vs. Logics on Data Words

Michael Benedikt
Clemens Ley
Gabriele Puppis

Abstract The relationship between automata and logics has been investigated since the 1960s. In particular, it was shown how to determine, given an automaton, whether or not it is definable in first-order logic with label tests and the order relation, and for first-order logic with the successor relation. In recent years, there has been much interest in languages over an infinite alphabet. Kaminski and Francez introduced a class of automata called finite memory automata (FMA), that represent a natural analog of finite state machines. A FMA can use, in addition to its control state, a (bounded) number of registers to store and compare values from the input word. The class of data languages recognized by FMA is incomparable with the class of data languages defined by firstorder formulas with the order relation and an additional binary relation for data equality. We first compare the expressive power of several variants of FMA with several data word logics. Then we consider the corresponding decision problem: given an automaton A and a logic, can the language recognized by A be defined in the logic? We show that it is undecidable for several variants of FMA, and then investigate the issue in detail for deterministic FMA. We show the problem is decidable for first-order logic with local data comparisons – an analog of first-order logic with successor. We also show instances of the problem for richer classes of first-order logic that are decidable.

Details

TCS Journal 2005 Journal Article

Structural properties of XPath fragments

Michael Benedikt
Wenfei Fan
Gabriel Kuper

We study structural properties of each of the main sublanguages of navigational XPath (W3c Recommendation) commonly used in practice. First, we characterize the expressive power of these language fragments in terms of both logics and tree patterns. Second, we investigate closure properties, focusing on the ability to perform basic Boolean operations while remaining within the fragment. We give a complete picture of the closure properties of these fragments, treating XPath expressions both as functions of arbitrary nodes in a document tree, and as functions that are applied only at the root of the tree. Finally, we provide sound and complete axiom systems and normal forms for several of these fragments. These results are useful for simplification of XPath expressions and optimization of XML queries.

Details DOI

CSL Conference 2005 Conference Paper

Towards a Characterization of Order-Invariant Queries over Tame Structures

Michael Benedikt
Luc Segoufin

Abstract This work deals with the expressive power of logics on finite structures with access to an additional “arbitrary” linear order. The queries that can be expressed this way are the order-invariant queries for the logic. For the standard logics used in computer science, such as first-order logic, it is known that access to an arbitrary linear order increases the expressiveness of the logic. However, when we look at the separating examples, we find that they have satisfying models whose Gaifman Graph is complex – unbounded in valence and in treewidth. We thus explore the expressiveness of order-invariant queries over graph-theoretically well-behaved structures. We prove that first-order order-invariant queries over strings and trees have no additional expressiveness over first-order logic in the original signature. We also prove new upper bounds on order-invariant queries over bounded treewidth and bounded valence graphs. Our results make use of a new technique of independent interest: the application of algebraic characterizations of definability to show collapse results.

Details

CSL Conference 2000 Conference Paper

Definability over Linear Constraints

Michael Benedikt
H. Jerome Keisler

Abstract We settle a number of questions concerning definability in first order logics with an extra predicate symbol ranging over semi-linear sets. These questions are motivated by the constraint database model for representing spatial data. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions on the semi-linear sets considered.

Details