Author name cluster

Adrien Boiret

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.

5 papers

1 author row

I&C Journal 2023 Journal Article

Transduction from trees to graphs through folding

Martin Berglund
Henrik Björklund
Johanna Björklund
Adrien Boiret

We introduce a fold operation that realises a tree-to-graph transduction by merging selected nodes in the input tree to form a possibly cyclic output graph. The work is motivated by the increasing use of graph-based representations in semantic parsing. We show that a suitable class of graphs languages can be generated by applying the fold operation to regular unranked tree languages. We investigate two versions of the fold operation, one that preserves a depth-first ordering between the edges, and one that does not. Finally, we demonstrate that the time complexity for the associated non-uniform membership problem is solvable in polynomial time for the order-preserving version, and NP-complete for the order-cancelling one.

Details DOI

Highlights Conference 2022 Conference Abstract

Symbolic Register Tree Transducers with Symbolic Register Lookahead

Adrien Boiret

Symbolic automata and transducers are objects of formal languages that can process inputs on an infinite signature through a finite number of rules guarded by a finite representation of subsets of the input signature. In the case of transducers, output is described using functions from the input signature to the output signature. In this paper, we propose a symbolic formalism for deterministic top-down tree transducers with a bottom-up lookahead. These transducers first read a tree from the bottom up, annotating the input tree, then read this annotated tree with a top-down transducer that produces and output. In our proposed symbolic formalism, both of those machine possess a finite number of states and a finite number of registers that can store data, but not test or perform computations on their content. This class is quite expressive and is stable under composition. We study the complexity of its equivalence problem via reduction to classical finite alphabet deterministic top-down transducers. We also present the subclass where the top-down part of the symbolic transducer carries no register, and show that the reduction of the equivalence problem to the classical case is much more efficient under that restriction.

Details

Highlights Conference 2021 Conference Abstract

Active Learning of Sequential Transducers with Side Information about the Domain

Adrien Boiret

Active learning is a setting in which a student queries a teacher, through membership and equivalence queries, in order to learn a language. Performance on these algorithms is often measured in the number of queries required to learn a target, with an emphasis on costly equivalence queries. In graybox learning, the learning process is accelerated by foreknowledge of some information on the target. Here, we consider graybox active learning of subsequential string transducers, where a regular overapproximation of the domain is known by the student. We show that there exists an algorithm to learn subsequential string transducers with a better guarantee on the required number of equivalence queriesthan classical active learning. Joint work with Raphaël Berthon, Guillermo Perez, Jean-Francois Raskin

Details

I&C Journal 2017 Journal Article

Automata for unordered trees

Adrien Boiret
Vincent Hugot
Joachim Niehren
Ralf Treinen

We present a framework for defining automata for unordered data trees that is parametrised by the way in which multisets of children nodes are described. Presburger tree automata and alternating Presburger tree automata are particular instances. We establish the usual equivalence in expressiveness of tree automata and MSO for our framework. We then investigate subclasses of automata for unordered trees for which testing language equivalence is in P-time. Starting from automata in our framework that describe multisets of children by finite automata, we propose two approaches to do this deterministically. We show that confluent horizontal evaluation leads to polynomial-time emptiness and universality, but coNP-complete emptiness and intersection. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as Counting Mso.

Details DOI

GandALF Workshop 2014 Workshop Paper

Deterministic Automata for Unordered Trees

Adrien Boiret
Vincent Hugot
Joachim Niehren
Ralf Treinen

Automata for unordered unranked trees are relevant for defining schemas and queries for data trees in Json or Xml format. While the existing notions are well-investigated concerning expressiveness, they all lack a proper notion of determinism, which makes it difficult to distinguish subclasses of automata for which problems such as inclusion, equivalence, and minimization can be solved efficiently. In this paper, we propose and investigate different notions of "horizontal determinism", starting from automata for unranked trees in which the horizontal evaluation is performed by finite state automata. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers from coNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as CMso.

PDF Details DOI