6 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…
Earliest query answering over streamed trees
Mateusz Gienieczko, MartÃn Muñoz, Filip Murlak +1
Streaming allows executing queries over massive JSON or XML documents whose size makes it infeasible to fully parse them into a tree. Earliest query answering is a radical approach…
A canonical generalization of OBDD
Florent Capelli, YooJung Choi, Stefan Mengel +2
We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respe…
Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
MartÃn Muñoz
We present an algorithm that, given an index , produces the -th (lexicographically ordered) answer of an MSO query over a string. The algorithm requires linear-time preproces…
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 …
Constant-delay enumeration for SLP-compressed documents
MartÃn Muñoz, Cristian Riveros
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a cont…