Length: 10 hours - 2 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 2
Recent years witnessed the revival of a traditional sub-class of Deterministic Context-Free languages: Operator Precedence languages (OPLs), originally introduced by Floyd in 1963. OPLs enjoy all the closure properties of Regular, McNaughton's Parenthesis, and Visibly Pushdown languages (introduced as Input Driven languages), yet are more expressive.
The course will start presenting the historical definitions and traditional usage of OPLs. Then the recent automata-theoretic and logic characterizations of OPLs, and omega languages will be covered, and their relation with automatic verification. The last part on OPLs will be on the suitability of OPLs for parallel parsing, with hints toward the parallel querying of data definition languages for Big Data applications.
Suggested Readings: Basics on discrete mathematics, formal language and automata, logics
Dates & Venue
| Giorni | Aula | Orario |
| 12/02/2019 |
Meeting Room 3rd floor - Via Celoria 18 - 20133 Milano The lesson has been postponed: 15/02/2019 |
10:30-13:30 |
| 20 /02/2019 | Meeting Room 3rd floor - Via Celoria 18 - 20133 Milano | 10:30-14:30 |
| 21/02/2019 | Meeting Room 3rd floor - Via Celoria 18 - 20133 Milano | 13:30-16:30 |
Lecturer:
Dr. ssa Violetta Lonati, Prof. Matteo Pradella
Assessor:
Dr.ssa Violetta Lonati