Research | Automata and Formal Languages

The group has a long research activity in the field of Automata and Formal Language theory, an established area of computer science, originating from the needs of early computer/communication systems and programming languages.In this framework, it deals with problems at the crossroad of theoretical computer science, mathematics and applications. The main topics of research are:

• Finite state automata and regular languages
• Variable-length codes
• Combinatorics on words
• Two-dimensional languages

The lines of research often cover two or more of the aforementioned areas. In particular, some of the investigated topics are the following ones:

• Structural properties of the variable-length codes and their relations with the theory of automata and formal power series
• Relationships among codes, combinatorics on words and free groups
• Extensions of the theory of codes to the two-dimensional case
• Combinatorics properties and recognizability issues of the two-dimensional languages
• Algorithms and data structures for the two-dimensional languages
• Computational models inspired by the biology (splicing systems)
• Applications of the combinatorics on words to bioinformatics and data compression
• Applications of the splicing system theory to the musical composition

Teaching activity

The group's teaching commitment is concentrated on the degree courses in Computer Science and specifically on Computer Architectures, Elements of the theory of computation, Mathematical methods for computer science, Design of algorithms, and Programming courses.

Collaborations: prof. Valérie Berthé (CNRS, Université Paris Diderot), prof. Paola Bonizzoni (Università di Milano Bicocca), prof. Dora Giammarresi (Università di Roma Tor Vergata), prof. Marina Madonia (Università di Catania), prof. Sabrina Mantaci (Università di Palermo), prof. Dominique Perrin (Université Paris Est), prof. Antonio Restivo (Università di Palermo), prof. Christophe Reutenauer (Université du Québec à Montréal), prof. Giuseppina Rindone (Université Paris Est).