Fixed point languages of rational transductions.
Fixed points of endomorphisms of certain free products
The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.
Fixed points of endomorphisms of certain free products
The fixed point submonoid of an endomorphism of a free product of a free monoid and cyclic groups is proved to be rational using automata-theoretic techniques. Maslakova’s result on the computability of the fixed point subgroup of a free group automorphism is generalized to endomorphisms of free products of a free monoid and a free group which are automorphisms of the maximal subgroup.
Fixpoint alternation : arithmetic, transition systems, and the binary tree
Fixpoint alternation: arithmetic, transition systems, and the binary tree
We provide an elementary proof of the fixpoint alternation hierarchy in arithmetic, which in turn allows us to simplify the proof of the modal mu-calculus alternation hierarchy. We further show that the alternation hierarchy on the binary tree is strict, resolving a problem of Niwiński.
Fixpoints, games and the difference hierarchy
Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.
Fixpoints, games and the difference hierarchy
Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.
Fonction de Carlitz et automates
Carlitz a défini sur une fonction et une série formelle , analogues respectivement à la fonction de Riemann et au réel . Yu a montré, en utilisant les modules de Drinfeld, que est transcendant pour tout non divisible par . Nous donnons ici une preuve «automatique» de la transcendance de pour , en utilisant le théorème de Christol, Kamae, Mendès France et Rauzy.
Fonctions hypergéométriques bornées
Forbidden factors and fragment assembly
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word from a given set of substrings (fragments) of a word . We introduce an hypothesis involving the set of fragments and the maximal length of the minimal forbidden factors of . Such hypothesis allows us to reconstruct uniquely the word from the set in linear...
Forbidden Factors and Fragment Assembly
In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments) of a word w. We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w. Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear...
Foreword
Formal language properties of hybrid systems with strong resets
We study hybrid systems with strong resets from the perspective of formal language theory. We define a notion of hybrid regular expression and prove a Kleene-like theorem for hybrid systems. We also prove the closure of these systems under determinisation and complementation. Finally, we prove that the reachability problem is undecidable for synchronized products of hybrid systems.
Formal language theory and the geometry of 3-manifolds.
Formal languages in dynamical systems
Formal Methods to Improve Public Administration Business Processes
Starting from late 90’s the public administration has started to employ a quite relevant amount of its budget in developing ICT solutions to better deliver services to citizens. In spite of this effort many statistics show that the mere availability of ICT based services does not guarantee per se their usage. Citizens have continued to largely access services through “traditional” means. In our study we suggest that the highlighted situation is partly due to the fact that relevant domain dependent...
Formal Methods to Improve Public Administration Business Processes
Starting from late 90’s the public administration has started to employ a quite relevant amount of its budget in developing ICT solutions to better deliver services to citizens. In spite of this effort many statistics show that the mere availability of ICT based services does not guarantee per se their usage. Citizens have continued to largely access services through “traditional” means. In our study we suggest that the highlighted situation is partly...
Formal Specifications in Software Development: an Overview
Formal translation directed by parsing
Formalized models of ontological systems