Programmes languages




Скачать 122.07 Kb.
НазваниеProgrammes languages
страница1/7
Дата03.10.2012
Размер122.07 Kb.
ТипДокументы
  1   2   3   4   5   6   7
4th International PhD School in Formal Languages and Applications


2005


1st TERM

Programmes




LANGUAGES


Zoltán Ésik, Rovira i Virgili University, Tarragona

zoltan.esik@urv.net


  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



Hopcroft, J.E., R. Motwani & J.D. Ullman (2000), Introduction to Automata Theory, Languages, and Computation, 3rd ed. Addison-Wesley, Reading, MA.

Papadimitriou, C. (1994), Computational Complexity. Addison-Wesley, Reading, MA.

Rozenberg, G. & A. Salomaa, eds. (1997), Handbook of Formal Languages, 3 vols. Springer, Berlin.

Salomaa, A. (1973), Formal Languages. Academic Press, New York.

COMBINATORICS ON WORDS


Tero Harju, University of Turku

harju@utu.fi


  1. Defect theorem

  2. Critical factorization theorem

  3. Ehrenfeucht’s conjecture



References



Lothaire, M. (1983), Combinatorics on Words. Addison-Wesley, Reading, MA.

Lothaire, M. (2002), Algebraic Combinatorics of Words. Cambridge University Press, Cambridge.

VARIETIES OF FORMAL LANGUAGES


Jean-Éric Pin, CNRS and University Paris 7

jean-eric.pin@liafa.jussieu.fr


  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



To be distributed.

REGULAR GRAMMARS


Masami Ito, Kyoto Sangyo University

ito@ksuvx0.kyoto-su.ac.jp


  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



Hopcroft, J.E. & J.D. Ullman (1979), Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA.

Ito, M. (2004), Algebraic Theory of Automata and Languages. World Scientific, Singapore.

Salomaa, A. (1981), Jewels of Formal Language Theory. Computer Science Press, Rockville, MD.

CONTEXT-FREE GRAMMARS


Manfred Kudlek, University of Hamburg

kudlek@informatik.uni-hamburg.de


  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



  1   2   3   4   5   6   7

Похожие:

Programmes languages iconProgrammes fuzzy formal languages

Programmes languages iconThe programmes of study

Programmes languages iconDescription of Programmes 3

Programmes languages iconShort Term Programmes

Programmes languages iconMa / msc programmes 2011/12

Programmes languages iconGoal and tasks of Programmes 3

Programmes languages iconList of Study Programmes and Workplaces

Programmes languages iconList of Study Programmes and Workplaces

Programmes languages iconTilapia research programmes in the Institute of Aquaculture

Programmes languages iconRevised Syllabus for msc(forestry) Programmes

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница