Formal languages and automata to model complex structures - Modul 1 - FROM 11/02/2019 TO 18/02/2019

Length: 15 hours - 3 cfu

Abstract

The course aims at presenting a number of different recent theoretical models and classes of formal languages, suitable for many different applications, e.g. verification of infinite-state systems, pattern recognition, paallel parsing, bio-inspired computing.
This is a joint course between Politecnico di Milano and Università degli Studi di Milano. The course is divided in two parts, presenting two recent and interesting families of models, suitable for many applications: one is on Operator Precedence languages, while the other is on Two-Dimensional languages.
part 1
A picture is a rectangular array of letters and a picture language (or 2D language) is a set of pictures. The course will survey many formal methods that have been proposed to define 2D languages, starting in most cases from a generalization to 2D of 1D (i.e., string) models: regular expressions, homomorphic characterizations, finite automata, and context-free grammars. We will contrast the formal properties enjoyed by each model in 1D versus 2D, and illustrate the strength and weakness of each model by using language examples.
After the basic 2D regular expressions, tiling systems will be presented as a central model. For automata, we will consider the historical 4-ways automata, the on-line tessellation acceptors, and several recent versions of tiling automata, sgraffito and restarting automata. For grammars, a polynomial-time parsing algorithm will be presented.
Relevant formal properties, such as closure under basic operations and known facts about decidability and complexity, together with relations of inclusion and incomparability between language families are presented too. Suggested Readings: Basics on discrete mathematics, formal language and automata, logics

Dates & Venue

Lecturer:

Dr.ssa Violetta Lonati. Prof. Matteo Pradella 

Assessor:

Dr.ssa Violetta Lonati