Programmes languages

Programmes

LANGUAGES

1. 
   Types of languages (languages of finite and infinite words, finite and infinite trees, graphs, pictures, etc.) and types of representation. Formal languages in mathematics and computer science
   
2. 
   Families of languages. Operations on languages (general operations on sets, specific operations). Closure of families of languages under operations. Abstract families of languages. Characterizations and representations of families of languages
   
3. 
   Decidability problems on languages. Descriptional complexity measures for languages. Languages and computational complexity
   

References

COMBINATORICS ON WORDS

1. 
   Defect theorem
   
2. 
   Critical factorization theorem
   
3. 
   Ehrenfeucht’s conjecture
   

References

VARIETIES OF FORMAL LANGUAGES

1. 
   Rational and recognizable sets
   
2. 
   Finite automata and recognizable sets
   
3. 
   Automata and semigroups
   
4. 
   A bit of history...
   
5. 
   Star-free languages
   
6. 
   Piecewise testable languages
   
7. 
   Locally testable languages
   
8. 
   Varieties, Eilenberg's theorem
   
9. 
   Elementary semigroup theory
   
10. 
    More examples of varieties
    
11. 
    Overview of recent advances
    

References

REGULAR GRAMMARS

1. 
   Regular grammars and languages
   
2. 
   Syntactic congruences
   
3. 
   Deterministic and nondeterministic automata
   
4. 
   Operations on languages
   
5. 
   Shuffle products and closures
   
6. 
   Directable automata and languages
   

References

CONTEXT-FREE GRAMMARS

1. 
   Normal forms
   
2. 
   Iteration lemmata
   
3. 
   Derivation trees, ambiguity
   
4. 
   Relation to pushdown automata
   
5. 
   Deterministic context-free languages
   
6. 
   Complexity of analysis
   
7. 
   Decidability problems
   
8. 
   Closure properties
   
9. 
   Algebraic characterization