Publications (8)
An ExpTime Upper Bound for with Integers (Extended Version)
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 sign…
A Neurosymbolic Approach to Natural Language Formalization and Verification
Chenyang An, Sam Bayless, Stefano Buliani +27
The paper presents ARc, a system that combines large language models with automated reasoning to formally translate natural‑language policies and verify their logical correctness,…
Hankel Matrices for Weighted Visibly Pushdown Automata
Nadia Labai, Johann A. Makowsky
Hankel matrices (aka connection matrices) of word functions and graph parameters have wide applications in automata theory, graph theory, and machine learning. We give a characteri…
Logics of Finite Hankel Rank
Nadia Labai, Johann A. Makowsky
We discuss the Feferman-Vaught Theorem in the setting of abstract model theory for finite structures. We look at sum-like and product-like binary operations on finite structures an…
Pebble-Intervals Automata and FO2 with Two Orders (Extended Version)
Nadia Labai, Tomer Kotek, Magdalena Ortiz +1
We introduce a novel automata model, called pebble-intervals automata (PIA), and study its power and closure properties. PIAs are tailored for a decidable fragment of FO that is im…
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…
Finiteness conditions for graph algebras over tropical semirings
Nadia Labai, Johann A. Makowsky
Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lov{á}sz and A. Schrijver (2007). Graph parameters with connection matrices…
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 which are known to be representable as partition functions which count the number of weighted homomorphisms into…