Michel de Rougemont

TCS Journal 2016 Journal Article

Approximate consistency for transformations on words and trees

• Michel de Rougemont
• Adrien Vieilleribière

We introduce approximate Source-consistency, for transformations of words and trees, the relaxed version of the Source-consistency problem. A setting consists in an input schema, an output schema and a relation T between input and output structures. Given an input structure I, we want to decide if there is an output structure J in the output schema such that ( I, J ) ∈ T. We consider transducers of words and trees and prove the testability of this property for some edit distance on words and trees. We exhibit randomized algorithms which distinguish between a consistent and an ε-far from consistent I, by looking at a constant fraction of the large input I. The main result on trees is based on a statistical representation of ordered unranked trees, which may be used in other contexts.

CSL Conference 2003 Conference Paper

Automata on Lempel-ziv Compressed Strings

• Hans Leiss
• Michel de Rougemont

Abstract Using the Lempel-Ziv-78 compression algorithm to compress a string yields a dictionary of substrings, i. e. an edge-labelled tree with an order-compatible enumeration, here called an LZ -trie. Queries about strings translate to queries about LZ -tries and hence can in principle be answered without decompression. We compare notions of automata accepting LZ -tries and consider the relation between acceptable and MSO-definable classes of LZ -tries. It turns out that regular properties of strings can be checked efficiently on compressed strings by LZ -trie automata.

TCS Journal 2002 Journal Article

The expressiveness of DAC

• Foto Afrati
• Irène Guessarian
• Michel de Rougemont

We define a new logic-based query language, called DAC, which is an extension of Datalog. A DAC(w(n), h(n))(b(n))-program consists of a family of Datalog programs Pn such that w(n), h(n), b(n) bound the width of rules, the number of rules, and the recursion depth of any Pn, respectively. We exhibit queries which are not Datalog expressible but are DAC expressible. We also prove non-expressiveness results for DAC and we infer various strict hierarchies obtained by allowing more rapidly growing functions on the bound parameters.

AAAI Conference 1997 Conference Paper

Spatial Navigation with Uncertain Deviations

• Michel de Rougemont

MFCS Conference 1997 Conference Paper

The Expressiveness of Datalog Circuits (DAC)

• Foto N. Afrati
• Irène Guessarian
• Michel de Rougemont

Abstract We define a new logic query language, called DAC, which is an extension of Datalog. We exhibit queries which are not Datalog expressible but are DAC expressible. We also prove non-expressiveness results for DAC and we infer various strict hierarchies obtained by allowing more rapidly growing functions on the bound parameters.

TCS Journal 1996 Journal Article

On the complexity of partially observed Markov decision processes

• Dima Burago
• Michel de Rougemont
• Anatol Slissenko

In the paper we consider the complexity of constructing optimal policies (strategies) for some type of partially observed Markov decision processes. This particular case of the classical problem deals with finite stationary processes, and can be represented as constructing optimal strategies to reach target vertices from a starting vertex in a graph with colored vertices and probabilistic deviations from an edge chosen to follow. The colors of the visited vertices is the only information available to a strategy. The complexity of Markov decision in the case of perfect information (bijective coloring of vertices) is known and briefly surveyed at the beginning of the paper. For the unobservable case (all the colors are equal) we give an improvement of the result of Papadimitriou and Tsitsiklis, namely we show that the problem of constructing even a very weak approximation to an optimal strategy is NP-hard. Our main results concern the case of a fixed bound on the multiplicity of coloring, that is a case of partially observed processes where some upper bound on the unobservability is supposed. We show that the problem of finding an optimal strategy is still NP-hard, but polytime approximations are possible. Some relations of our results to the Max-Word Problem are also indicated.

ICRA Conference 1992 Conference Paper

A theory of robust planning

• Michel de Rougemont
• Juan Francisco Díaz-Frías

A notion of robustness for planning problems is introduced in a model with uncertainty, based on a global probabilistic model. The authors define the notion of a robust strategy within this model, which allows comparison of different strategies. They then study how an outside observer would know in advance the level of robustness of a system. The analysis is based on the complexity class IP, the class of problems that can be efficiently verified by a random interactive proof system. The approach was applied to a mobile robot trying to execute a plan in a geometrical environment following a strategy that uses various sensors to cope with the uncertainty. Various examples of robust and nonrobust strategies are given. >

TCS Journal 1992 Journal Article

The functional dimension of inductive definitions

• Michel de Rougemont

If R(x, y) is an inductively defined relation, we say that x and y are dependent, if there exists a function ⨍ such that ∀x, y R(x, y) ⇔ R(x, f(x)). The functional dimension of an inductive query is the number of independent recursion variables, and is an important logical property of R, related to its efficient evaluation. In this paper, we compare the expressive power of various languages: the language of iterated inductive definitions, the stratified logic programs and second-order logic. The functional dimension is an important parameter in this comparison. We prove that on the class of finite-valued graphs with a successor relation, the query SP, where SP(a, b, i) if the shortest path between a and b is of cost, i, is not monadic second-order definable, i. e. it cannot be defined by a second-order formula with existential and universal second-order quantifiers on monadic relations. We then conclude that it can neither be defined by iterated inductions with one recursion variable, nor by stratified logic programs with one recursion variable. We prove that in the general case it is undecidable to determine if an inductive query is of functional dimension 1, although it can be decidable in certain cases.

IJCAI Conference 1987 Conference Paper

Constructive Second-Order Proofs in Logical Databases

• Michel de Rougemont

STOC Conference 1984 Conference Paper

Uniform Definability on Finite Structures with Successor

• Michel de Rougemont