1 citations · 2 across the 11 of their papers we have counts for
9 papers · 1 filter
Topological Complexity of omega-Powers : Extended Abstract
Olivier Finkel, Dominique Lecomte
This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper "Classical and effective descriptive complexities o…
On Infinite Real Trace Rational Languages of Maximum Topological Complexity
Olivier Finkel, Jean-Pierre Ressayre, Pierre Simonnet
We consider the set of infinite real traces, over a dependence alphabet (Gamma, D) with no isolated letter, equipped with the topology induced by the prefix metric. We then prove t…
An omega-Power of a Finitary Language Which is a Borel Set of Infinite Rank
Olivier Finkel
Omega-powers of finitary languages are omega languages in the form V^omega, where V is a finitary language over a finite alphabet X. Since the set of infinite words over X can be e…
On the Length of the Wadge Hierarchy of Omega Context Free Languages
Olivier Finkel
We prove in this paper that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal epsilon_omega, which is the omega-th fixed point of…
Topology and Ambiguity in Omega Context Free Languages
Olivier Finkel, Pierre Simonnet
We study the links between the topological complexity of an omega context free language and its degree of ambiguity. In particular, using known facts from classical descriptive set…
Undecidable Problems About Timed Automata
Olivier Finkel
We solve some decision problems for timed automata which were recently raised by S. Tripakis in [ Folk Theorems on the Determinization and Minimization of Timed Automata, in the Pr…