5 papers
A simple algorithmic framework for disambiguation of finite automata
Mauricio Cari, MartÃn Muñoz, Cristian Riveros
We study the task of disambiguation of finite state automata, namely, converting an automaton into an equivalent, unambiguous one. We do this by developing a novel and simple algor…
Dynamic direct access of MSO query evaluation over strings
Pierre Bourhis, Florent Capelli, Stefan Mengel +1
We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query w…
Using Color Refinement to Boost Enumeration and Counting for Acyclic CQs of Binary Schemas
Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt
We present an index structure, called the color-index, to boost the evaluation of acyclic conjunctive queries (ACQs) over binary schemas. The color-index is based on the color refi…
Structural Indexing of Relational Databases for the Evaluation of Free-Connex Acyclic Conjunctive Queries
Cristian Riveros, Benjamin Scheidt, Nicole Schweikardt
We present an index structure to boost the evaluation of free-connex acyclic conjunctive queries (fc-ACQs) over relational databases. The main ingredient of the index associated wi…
Active Learning of Symbolic Automata Over Rational Numbers
Sebastian Hagedorn, MartÃn Muñoz, Cristian Riveros +1
Automata learning has many applications in artificial intelligence and software engineering. Central to these applications is the algorithm, introduced by Angluin. The …