Author name cluster

Andrei Draghici

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.

3 papers

2 author rows

CSL Conference 2025 Conference Paper

Boundedness of Cost Register Automata over the Integer Min-Plus Semiring

Andrei Draghici
Radoslaw Piórkowski
Andrew Ryzhikov

Cost register automata (CRAs) are deterministic automata with registers taking values from a fixed semiring. A CRA computes a function from words to values from this semiring. CRAs are tightly related to well-studied weighted automata. Given a CRA, the boundedness problem asks if there exists a natural number N such that for every word, the value of the CRA on this word does not exceed N. This problem is known to be undecidable for the class of linear CRAs over the integer min-plus semiring (ℤ∪{+∞}, min, +), but very little is known about its subclasses. In this paper, we study boundedness of copyless linear CRAs with resets over the integer min-plus semiring. We show that it is decidable for such CRAs with at most two registers. More specifically, we show that it is, respectively, NL-complete and in coNP if the numbers in the input are presented in unary and binary. We also provide complexity results for two classes with an arbitrary number of registers. Namely, we show that for CRAs that use the minimum operation only in the output function, boundedness is PSPACE-complete if transferring values to other registers is allowed, and is coNP-complete otherwise. Finally, for each f_i in the hierarchy of fast-growing functions, we provide a stateless CRA with i registers whose output exceeds N only on runs longer than f_i(N). Our construction yields a non-elementary lower bound already for four registers.

Details

Highlights Conference 2023 Conference Abstract

Semenov Arithmetic, Affine VASS, and String Constraints

Andrei Draghici

We study extensions of Semenov arithmetic, the first-order theory of the structure $\langle \mathbb{N}, +, 2^x\rangle$. It is well-known that this theory becomes undecidable when extended with regular predicates over number strings, such as the Büchi $V_2$-predicate. We therefore restrict ourselves to the existential theory of Semenov arithmetic and show that this theory is decidable in 2-EXPSPACE when extended with arbitrary regular predicates over number strings. Our approach relies on a reduction to the emptiness problem for a restricted class of affine vector addition systems with states, which we show decidable in EXPSPACE. As an application of our result, we settle an open problem from the literature and show decidability of a class of string constraints involving length constraints. Contributed talk given by Andrei Draghici

Details

AAAI Conference 2022 Conference Paper

On the Complexity of Inductively Learning Guarded Clauses

Andrei Draghici
Georg Gottlob
Matthias Lanzinger

We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the ΣP 2 -complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to k-guarded clauses for constant k.

PDF Details