Project presentation
This research project focuses on formal languages and automata and aims at advancing the theory of these topics and their applications to technological and scientific problems. Formal Languages and Automata theory, one of the longest established areas in Computer Science, still offers complex open problems and research lines in many different directions.
Indeed, on the one hand, new applications of automata-theoretic concepts have emerged in addition to the more classical applications such as pattern matching, syntax analysis and software verification. These include system analysis and verification, natural language processing, information retrieval, data compression, and control of discrete event systems. Furthermore, new challenges for automata theory include biology, network security, quantum computing, tomography, picture processing.
On the other hand, some deep questions of classical theory are still open and new theoretical problems also arise from applications. This is why the mathematical foundations of this theory rely on more and more advanced parts of mathematics. While in the early sixties only elementary graph theory and combinatorics were required, new tools from non-commutative algebra, logic, probability theory and symbolic dynamics have been introduced successively and the latest developments borrow ideas from topology and geometry. For instance, combinatorics of finite or infinite sequences of symbols of a finite alphabet has been developed considerably in the last years and has been extended to combinatorial structures which are more general than words, namely trees and pictures.
Obviously, significant technical developments need significant theoretical progress. Thus, unsurprisingly, fundamental results are even more necessary after the emergence of the new applications listed above.
The aim of the project is to develop research in the area of formal languages and automata (both for theoretical models and applications in specific fields) integrating the different expertise of the units participating in the project. The research project focuses on a limited range of topics. More specifically, we plan to develop the following lines of research:
- Automata models, formal series, and their properties:
- Quantum automata
- Descriptional complexity measures for languages
- Suffix automata and their applications to text indexing
- Flower automata and their applications to variable-length codes
- Schutzenberger automata and relative algorithms
- k-synchronizing and k-collapsing words
- Techniques of symbolic manipulation for formal languages.
- Words, codes and combinatorial structures.
- Combinatorial, structural, and arithmetical properties of the Sturmian words and their generalizations
- Avoidable regularities and repetitiveness in infinite words
- Pattern statistics
- Burrows-Wheeler Transform
- Applications of combinatorics on words to Data Compression
- Extension of combinatorics on words to labelled trees
- Enumerative and algebraic combinatorics
- Exhaustive generation and Gray codes
- Structural properties of variable-length codes
- Grammars and unconventional representations for formal languages.
- Parentheses languages and context-free grammars
- Counting functions of context-free languages
- Context-free probabilistic grammars and their applications to natural language processing
- Syntax-directed translation schemata (SDTS), tree automata and their applications to natural language translation
- Associative models for language definition: Consensual grammars, Associative Language Descriptions
- Molecular computation systems
- Characterization of the regular languages generated by finite (linear and circular) splicing systems
- Two-dimensional languages and structures
- Tiling recognizable languages
- Deterministic and unambiguous models
- Formal series in 2D
- Generalization of regular expressions in 2D
- Decision problems for two-dimensional languages
- Image classification and pattern recognition based on grammars and tilings, and their applications
- Combinatorial properties of permutominoes
- Uniqueness and stability problems for reconstruction algorithms in geometrical and discrete tomography
- Cellular automata, symbolic dynamics and associated languages, decision problems
- Formal models of distributed systems
- Trace languages
- Models of parallel computation based on trace theory motivated by code compilation
- Models for web analysis
- System analysis and verification: models and their decision problems for infinite state systems
- Satisfiable temporal logics for real-time system verification