Automata

Solving Language Equations Using Flanked Automata

We define a new subclass of nondeterministic finite automata for prefix-closed languages called Flanked Finite Automata (FFA). Our motivation is to provide an efficient way to compute the quotient and inclusion of regular languages …

On the Complexity of Flanked Finite State Automata

We define a new subclass of nondeterministic finite automata for prefix-closed languages called Flanked Finite Automata (FFA). We show that this class enjoys good complexity properties while preserving the succinctness of …

TraLaLa

Nov 2004 — Feb 2008. TraLaLA, XML Transformation Languages: logic and applications, is a project funded by ACI MASSES DE DONNÉES. The objectives of the project is to study the processing, querying and manipulation of _data-masses_ (large amounts of data) available in XML format.

A Concurrent Calculus with Atomic Transactions

The _Software Transactional Memory_ (STM) model is an original approach for controlling concurrent accesses to ressources without the need for explicit lock-based synchronization mechanisms. A key feature of STM is to provide a way …

A Concurrent Calculus with Atomic Transactions

The _Software Transactional Memory_ (STM) model is an original approach for controlling concurrent accesses to ressources without the need for explicit lock-based synchronization mechanisms. A key feature of STM is to provide a way …

XML schema, tree logic and sheaves automata

XML documents may be roughly described as unranked, ordered trees and it is therefore natural to use tree automata to process or validate them. This idea has already been successfully applied in the context of Document Type …

A Logic you Can Count On

We prove the decidability of the quantifier-free, static fragment of ambient logic, with composition adjunct and iteration, which corresponds to a kind of regular expression language for semistructured data. The essence of this …

XML Schema, Tree Logic and Sheaves Automata

XML documents, and other forms of semi-structured data, may be roughly described as edge labeled trees; it is therefore natural to use tree automata to reason on them. This idea has already been successfully applied in the context …

Multitrees Automata, Presburger's Constraints and Tree Logics

We describe _multitree automata_ and a related logic on multitrees. Multitrees are extensions of trees with both associative and associative-commutative symbols that may bear arbitrary numbers of sons. An originality of our approach …