Author name cluster

Nadia Labai

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.

4 papers

2 author rows

KR Conference 2020 Conference Paper

An ExpTime Upper Bound for ALC with Integers

Nadia Labai
Magdalena Ortiz
Mantas Šimkus

Concrete domains, especially those that allow to compare features with numeric values, have long been recognized as a very desirable extension of description logics (DLs), and significant efforts have been invested into adding them to usual DLs while keeping the complexity of reasoning in check. For expressive DLs and in the presence of general TBoxes, for standard reasoning tasks like consistency, the most general decidability results are for the so-called ω-admissible domains, which are required to be dense. Supporting non-dense domains for features that range over integers or natural numbers remained largely open, despite often being singled out as a highly desirable extension. The decidability of some extensions of ALC with non-dense domains has been shown, but existing results rely on powerful machinery that does not allow to infer any elementary bounds on the complexity of the problem. In this paper, we study an extension of ALC with a rich integer domain that allows for comparisons (between features, and between features and constants coded in unary), and prove that consistency can be solved using automata-theoretic techniques in single exponential time, and thus has no higher worst-case complexity than standard ALC. Our upper bounds apply to some extensions of DLs with concrete domains known from the literature, support general TBoxes, and allow for comparing values along paths of ordinary (not necessarily functional) roles.

PDF Details DOI

MFCS Conference 2016 Conference Paper

On the Exact Learnability of Graph Parameters: The Case of Partition Functions

Nadia Labai
Johann A. Makowsky

We study the exact learnability of real valued graph parameters f which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph H with vertex weights alpha and edge weights beta. M. Freedman, L. Lovasz and A. Schrijver have given a characterization of these graph parameters in terms of the k-connection matrices C(f, k) of f. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter f, the learner can ask for the values of f for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices C(f, k) of f. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of H and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.

Details

Highlights Conference 2015 Conference Abstract

Eliminating Logic from Meta Theorems

Nadia Labai

A meta theorem, in our context, is a statement about a logic L of the form: ``If a graph parameter f is definable in L, then it is computable in polynomial time over graph classes of a certain kind. '' A famous example is Courcelle’s theorem, which states that the definability of graph properties in Monadic Second Order Logic implies they are linear time computable over graph classes of bounded tree-width. In 1998 the theorem was generalized to graph parameters and graph classes of bounded clique-width by Courcelle, Makowsky, and Rotics. In 2004, J. A. Makowsky gave a further generalized meta theorem involving sum-like inductive graph classes, which are inductively defined using a finite set of basic graphs and a finite set of binary sum-like operations. We eliminate logic from these meta theorems by replacing their definability conditions with finiteness conditions on Hankel matrices. A Hankel matrix H(f, \Box) for a graph parameter f and a binary operation \Box on graphs is an infinite matrix where the rows and columns are labeled with graphs, and the entry corresponding to the row labeled with G and the column labeled with G' is given by the value f(G \Box G'). We show that the graph parameters covered by our logic-free treatment are a proper superset of the graph parameters covered by the meta theorems involving logic. Joint work with J. A. Makowsky.

Details

GandALF Workshop 2013 Workshop Paper

Weighted Automata and Monadic Second Order Logic

Nadia Labai
Johann A. Makowsky

Let S be a commutative semiring. M. Droste and P. Gastin have introduced in 2005 weighted monadic second order logic WMSOL with weights in S. They use a syntactic fragment RMSOL of WMSOL to characterize word functions (power series) recognizable by weighted automata, where the semantics of quantifiers is used both as arithmetical operations and, in the boolean case, as quantification. Already in 2001, B. Courcelle, J. Makowsky and U. Rotics have introduced a formalism for graph parameters definable in Monadic Second order Logic, here called MSOLEVAL with values in a ring R. Their framework can be easily adapted to semirings S. This formalism clearly separates the logical part from the arithmetical part and also applies to word functions. In this paper we give two proofs that RMSOL and MSOLEVAL with values in S have the same expressive power over words. One proof shows directly that MSOLEVAL captures the functions recognizable by weighted automata. The other proof shows how to translate the formalisms from one into the other.

PDF Details DOI