The ANR project FREC, Frontiers of recognizability, involves researchers of the LaBRI, the LIAFA and the LIFC. Its goal is to push further the frontiers of recent developments in the theory of automata and recognizability to more complex and realistic structures: trees, λ-terms and models of quantitative automata.
The challenge is to transfer, with effectiveness in mind, results successfully obtained in the context of finite words to these structures, ranging over infinite domains. These extensions are motivated by increasingly important applications, in particular in the fields of verification and computational linguistics. Such structures occur in the real world, for instance as behaviors of computer systems, or as inputs of data processing problems.
Our strategy is to exploit and expand the most recent developments of the theory of recognizable languages of finite words, of an algebraic and topological nature, as a guide and a blueprint for the construction of the theory of more complex structures required in applications.
You can download the full scientific project description.