Course Information

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
In-person direct teaching

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
Mgr. Juraj Major (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 25. 9. to Wed 18. 12. Wed 10:00–11:50 A218

• Timetable of Seminar Groups:

IA006/01: Thu 26. 9. to Thu 19. 12. each odd Thursday 14:00–15:50 A318, J. Major

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 10/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 29 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)
Mgr. Juraj Major (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 A319

• Timetable of Seminar Groups:

IA006/01: Wed 27. 9. to Wed 6. 12. each odd Wednesday 14:00–15:50 A217, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 18/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 54 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. David Klaška (assistant)
Mgr. Juraj Major (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 A320

• Timetable of Seminar Groups:

IA006/01: Thu 15. 9. to Thu 8. 12. each odd Thursday 14:00–15:50 A218, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 6/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 54 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. David Klaška (assistant)
Mgr. Juraj Major (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 15. 9. to Wed 8. 12. Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: Thu 16. 9. to Thu 14. 10. each odd Thursday 14:00–15:50 A218; and Thu 4. 11. 14:00–15:50 A218, Thu 18. 11. 14:00–15:50 A218, Thu 2. 12. 14:00–15:50 A218, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 3/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 53 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
Mgr. Juraj Major (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)
Mgr. Tatiana Zbončáková (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/02: each even Thursday 14:00–15:50 A218, J. Major, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 53 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
Mgr. Juraj Major (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Miriama Jánošová (assistant)
RNDr. David Klaška (assistant)
Mgr. Jakub Lédl (assistant)
Mgr. Tatiana Zbončáková (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/02: each odd Thursday 8:00–9:50 B411, J. Strejček
IA006/04: each odd Wednesday 14:00–15:50 A218, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 1/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 53 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
Mgr. Juraj Major (seminar tutor)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)
Bc. Tomáš Lamser (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 12:00–13:50 C511, J. Barnat
IA006/02: each odd Thursday 12:00–13:50 C511, J. Barnat
IA006/03: each even Thursday 14:00–15:50 A320, J. Strejček
IA006/04: each odd Thursday 14:00–15:50 A320, J. Strejček
IA006/05: each even Thursday 16:00–17:50 A320, J. Major
IA006/06: each odd Thursday 16:00–17:50 A320, J. Major

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 24 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (assistant)
Mgr. Juraj Major (seminar tutor)
RNDr. František Blahoudek, Ph.D. (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. David Klaška (assistant)
Mgr. Ľuboš Korenčiak, Ph.D. (assistant)
Bc. Tomáš Lamser (assistant)
RNDr. Henrich Lauko, Ph.D. (assistant)
RNDr. Vladimír Štill, Ph.D. (assistant)
Mgr. Martina Vitovská (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 8:00–9:50 B411, J. Barnat
IA006/02: each odd Thursday 8:00–9:50 B411, J. Barnat
IA006/03: each even Thursday 10:00–11:50 B411, J. Strejček
IA006/04: each odd Thursday 10:00–11:50 B411, J. Strejček
IA006/05: each even Thursday 12:00–13:50 B411, J. Major
IA006/06: each odd Thursday 12:00–13:50 B411, J. Major

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 24 fields of study the course is directly associated with, display

Course objectives

The main aim is to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship between finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective areas and to understand methods and techniques of their applications.

Learning outcomes

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, and to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (alternate examiner)
prof. RNDr. Jan Strejček, Ph.D. (alternate examiner)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
Mgr. Ľuboš Korenčiak, Ph.D. (seminar tutor)
RNDr. František Blahoudek, Ph.D. (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
RNDr. Henrich Lauko, Ph.D. (assistant)
RNDr. Vladimír Štill, Ph.D. (assistant)
Mgr. Eva Tesařová (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 12:00–13:50 C525, J. Barnat
IA006/02: each odd Thursday 12:00–13:50 C525, J. Barnat
IA006/03: each odd Monday 10:00–11:50 A318, V. Řehák
IA006/04: each even Monday 10:00–11:50 A318, V. Řehák
IA006/05: each odd Wednesday 14:00–15:50 C511, J. Strejček
IA006/06: each even Wednesday 14:00–15:50 C511, V. Řehák

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 24 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (alternate examiner)
prof. RNDr. Jan Strejček, Ph.D. (alternate examiner)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
Mgr. Ľuboš Korenčiak, Ph.D. (seminar tutor)
RNDr. František Blahoudek, Ph.D. (assistant)
Mgr. Bc. Tomáš Janík (assistant)
RNDr. Martin Jonáš, Ph.D. (assistant)
Mgr. Eva Tesařová (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Thu 16:00–17:50 D1

• Timetable of Seminar Groups:

IA006/T01: Mon 9:40–11:15 105, Wed 23. 9. to Tue 22. 12. Wed 14:40–16:15 117, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IA006/01: each even Thursday 10:00–11:50 C511, J. Barnat
IA006/02: each odd Thursday 10:00–11:50 C511, J. Barnat
IA006/03: each even Monday 8:00–9:50 C511, V. Řehák
IA006/04: each odd Monday 8:00–9:50 C511, V. Řehák
IA006/05: each even Wednesday 12:00–13:50 B410, V. Řehák
IA006/06: each odd Wednesday 12:00–13:50 B410, V. Řehák
IA006/07: each even Wednesday 10:00–11:50 B204, J. Strejček
IA006/08: each odd Wednesday 10:00–11:50 B204, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 24 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (alternate examiner)
prof. RNDr. Jan Strejček, Ph.D. (alternate examiner)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
doc. RNDr. Tomáš Brázdil, Ph.D. (seminar tutor)
Mgr. Karolína Malá (seminar tutor)
RNDr. František Blahoudek, Ph.D. (assistant)
Mgr. Bc. Tomáš Janík (assistant)
doc. RNDr. Petr Novotný, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Thu 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 12:00–13:50 A218, J. Barnat
IA006/02: each odd Thursday 12:00–13:50 A218, J. Barnat
IA006/03: each even Monday 8:00–9:50 B410, T. Brázdil
IA006/04: each odd Monday 8:00–9:50 B410, T. Brázdil
IA006/05: each even Monday 12:00–13:50 C511, K. Malá
IA006/06: each odd Monday 12:00–13:50 C511, K. Malá
IA006/07: each even Monday 10:00–11:50 C525, V. Řehák
IA006/08: each odd Monday 10:00–11:50 C525, V. Řehák
IA006/09: each even Wednesday 14:00–15:50 A217, J. Strejček
IA006/10: each odd Wednesday 14:00–15:50 A217, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 23 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (alternate examiner)
prof. RNDr. Jan Strejček, Ph.D. (alternate examiner)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
RNDr. František Blahoudek, Ph.D. (seminar tutor)
doc. RNDr. Tomáš Brázdil, Ph.D. (seminar tutor)
Mgr. Matúš Abaffy (assistant)
Mgr. Vojtěch Havel (assistant)
Mgr. Bc. Tomáš Janík (assistant)
RNDr. David Klaška (assistant)
doc. RNDr. Petr Novotný, Ph.D. (assistant)
RNDr. Mária Svoreňová, Ph.D. (assistant)
Mgr. Marek Tomáštík (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Mon 16:00–17:50 D1

• Timetable of Seminar Groups:

IA006/T01: Mon 13:00–14:55 Učebna S9 (55), Tue 17. 9. to Fri 20. 12. Tue 8:00–9:55 Učebna S9 (55), F. Blahoudek, T. Janík, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IA006/01: each odd Thursday 10:00–11:50 B411, J. Barnat
IA006/02: each even Thursday 10:00–11:50 B411, J. Barnat
IA006/03: each odd Thursday 8:00–9:50 G101, F. Blahoudek
IA006/04: each even Thursday 8:00–9:50 G101, F. Blahoudek
IA006/05: each odd Monday 10:00–11:50 G331, T. Brázdil
IA006/06: each even Monday 10:00–11:50 G331, T. Brázdil
IA006/07: each odd Tuesday 8:00–9:50 C416, V. Řehák
IA006/08: each even Tuesday 8:00–9:50 C416, V. Řehák
IA006/09: each odd Wednesday 10:00–11:50 B411, J. Strejček
IA006/10: each even Wednesday 10:00–11:50 B411, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 23 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
doc. RNDr. Tomáš Brázdil, Ph.D. (seminar tutor)
RNDr. Jan Krčál, Ph.D. (seminar tutor)
doc. RNDr. Petr Novotný, Ph.D. (seminar tutor)
doc. Mgr. Jan Obdržálek, PhD. (seminar tutor)
RNDr. Nikola Beneš, Ph.D. (assistant)
Mgr. Bc. Tomáš Janík (assistant)
RNDr. Mária Svoreňová, Ph.D. (assistant)
RNDr. Jana Tůmová, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics

Timetable

Wed 14:00–15:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Wednesday 16:00–17:50 G101, J. Strejček
IA006/02: each odd Wednesday 16:00–17:50 G101, J. Strejček
IA006/03: each even Thursday 10:00–11:50 G126, T. Brázdil
IA006/04: each odd Thursday 10:00–11:50 G126, T. Brázdil
IA006/05: each even Thursday 12:00–13:50 B410, J. Barnat
IA006/06: each odd Thursday 12:00–13:50 B410, J. Barnat
IA006/07: each even Thursday 14:00–15:50 G124, V. Řehák
IA006/08: each odd Thursday 14:00–15:50 G124, V. Řehák
IA006/09: each even Thursday 12:00–13:50 G126, J. Obdržálek
IA006/10: each odd Thursday 12:00–13:50 G126, J. Obdržálek
IA006/T01A: Thu 20. 9. to Fri 21. 12. Thu 14:00–15:55 Učebna S3 (37), J. Krčál, P. Novotný
IA006/T01AA: Mon 9:00–10:55 Učebna S3 (37), J. Krčál, P. Novotný

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 23 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Finite-state automata and monadic second-order logic
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
RNDr. Nikola Beneš, Ph.D. (seminar tutor)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
RNDr. Jana Tůmová, Ph.D. (assistant)
Mgr. Filip Štefaňák (seminar tutor)
Mgr. Bc. Tomáš Janík (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 14:00–15:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 10:00–11:50 G123, J. Barnat
IA006/02: each odd Thursday 10:00–11:50 G123, J. Barnat
IA006/03: each even Tuesday 12:00–13:50 B410, V. Řehák
IA006/04: each odd Tuesday 12:00–13:50 B410, V. Řehák
IA006/05: each even Thursday 16:00–17:50 G125, N. Beneš, M. Češka
IA006/06: each odd Thursday 16:00–17:50 G125, N. Beneš, M. Češka
IA006/07: each even Thursday 14:00–15:50 B204, J. Strejček
IA006/08: each odd Thursday 14:00–15:50 B204, J. Strejček
IA006/09: each even Friday 12:00–13:50 B204, F. Štefaňák
IA006/10: each odd Friday 12:00–13:50 B204, F. Štefaňák

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 24 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
RNDr. Nikola Beneš, Ph.D. (assistant)
doc. RNDr. Milan Češka, Ph.D. (seminar tutor)
RNDr. Jana Tůmová, Ph.D. (assistant)
RNDr. Václav Brožek, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 12:00–13:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 10:00–11:50 B204, J. Barnat
IA006/02: each odd Thursday 10:00–11:50 B204, J. Barnat
IA006/03: each even Thursday 12:00–13:50 B011, J. Barnat
IA006/04: each odd Thursday 12:00–13:50 B011, J. Barnat
IA006/05: each even Thursday 16:00–17:50 B011, J. Strejček
IA006/06: each odd Thursday 16:00–17:50 B011, J. Strejček
IA006/07: each even Wednesday 14:00–15:50 B410, V. Řehák
IA006/08: each odd Wednesday 14:00–15:50 B410, V. Řehák
IA006/09: each even Tuesday 16:00–17:50 B410, M. Češka
IA006/10: each odd Tuesday 16:00–17:50 B410, M. Češka

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 23 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
RNDr. Nikola Beneš, Ph.D. (assistant)
doc. RNDr. Milan Češka, Ph.D. (assistant)
RNDr. Jana Tůmová, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each odd Thursday 10:00–11:50 B007, J. Barnat
IA006/02: each even Thursday 10:00–11:50 B007, J. Barnat
IA006/03: each odd Thursday 12:00–13:50 B007, J. Barnat
IA006/04: each even Thursday 12:00–13:50 B007, J. Barnat
IA006/05: each odd Wednesday 14:00–15:50 B410, J. Strejček
IA006/06: each even Wednesday 14:00–15:50 B410, J. Strejček
IA006/07: each odd Friday 8:00–9:50 C511, V. Řehák
IA006/08: each even Friday 8:00–9:50 C511, V. Řehák

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256

fields of study / plans the course is directly associated with

there are 23 fields of study the course is directly associated with, display

Course objectives

At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Teaching methods

Lectures, exercises, and reading. Optional homeworks.

Assessment methods

One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
prof. RNDr. Jan Strejček, Ph.D. (seminar tutor)
RNDr. Václav Brožek, Ph.D. (assistant)
doc. RNDr. Milan Češka, Ph.D. (assistant)
RNDr. Vojtěch Forejt, Ph.D., LL.B. (Hons) (assistant)
RNDr. Jana Tůmová, Ph.D. (assistant)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 10:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 10:00–11:50 B204, J. Barnat
IA006/02: each odd Thursday 10:00–11:50 B204, J. Barnat
IA006/03: each even Thursday 12:00–13:50 B011, J. Barnat
IA006/04: each odd Thursday 12:00–13:50 B011, J. Barnat
IA006/05: each even Tuesday 10:00–11:50 B204, J. Strejček
IA006/06: each odd Tuesday 10:00–11:50 B204, J. Strejček

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

there are 19 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.

Assessment methods

Lectures and exercises. Optional homeworks. One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Mon 16:00–17:50 D2, Wed 12:00–13:50 D2

• Timetable of Seminar Groups:

IA006/01: each odd Thursday 10:00–11:50 B003, J. Barnat
IA006/02: each even Thursday 10:00–11:50 B003, J. Barnat
IA006/03: each odd Thursday 12:00–13:50 B003, J. Barnat
IA006/04: each even Thursday 12:00–13:50 B003, J. Barnat

Prerequisites

Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

there are 19 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 8:00–9:50 D1, Wed 12:00–13:50 D2

• Timetable of Seminar Groups:

IA006/01: each even Thursday 12:00–13:50 B410, J. Barnat
IA006/02: each odd Thursday 12:00–13:50 B410, J. Barnat
IA006/03: each even Thursday 14:00–15:50 B011, J. Barnat

Prerequisites

! I006 Automata II
Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

there are 6 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

Study Materials
The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 9:00–11:50 D1

• Timetable of Seminar Groups:

IA006/01: each even Thursday 16:00–17:50 B007, J. Barnat
IA006/02: each odd Thursday 16:00–17:50 B007, J. Barnat
IA006/03: each even Wednesday 12:00–13:50 B007, J. Barnat

Prerequisites

! I006 Automata II
Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

there are 6 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Mon 12:00–14:50 D2

• Timetable of Seminar Groups:

IA006/01: each even Thursday 14:00–15:50 B003
IA006/02: each even Thursday 16:00–17:50 B003

Prerequisites

! I006 Automata II
Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is only offered to the students of the study fields the course is directly associated with.

fields of study / plans the course is directly associated with

there are 6 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer), prof. RNDr. Ivana Černá, CSc. (deputy)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Thu 14:00–15:50 B410

• Timetable of Seminar Groups:

IA006/01: each odd Thursday 16:00–17:50 B411 and each even Thursday 16:00–17:50 B411, J. Barnat
IA006/02: No timetable has been entered into IS. J. Barnat

Prerequisites

! I006 Automata II
Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is only offered to the students of the study fields the course is directly associated with.

fields of study / plans the course is directly associated with

• Applied Informatics (programme FI, N-AP)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)

Course objectives

The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

IA006 Selected topics on automata theory

Extent and Intensity

2/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).

Teacher(s)

prof. RNDr. Mojmír Křetínský, CSc. (lecturer), prof. RNDr. Ivana Černá, CSc. (deputy)
prof. RNDr. Ivana Černá, CSc. (seminar tutor)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor), prof. RNDr. Ivana Černá, CSc. (deputy)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.

Timetable

Wed 15:00–17:50 D2

• Timetable of Seminar Groups:

IA006/01: each odd Thursday 14:00–15:50 B003, J. Barnat
IA006/02: each even Thursday 14:00–15:50 B003, J. Barnat
IA006/03: each odd Friday 8:00–9:50 B011, V. Řehák
IA006/04: each even Friday 8:00–9:50 B011, V. Řehák
IA006/Nza1p: No timetable has been entered into IS. M. Křetínský

Prerequisites

! I006 Automata II
Knowlegde corresponding to the course IB005 - Formal languages and automata and IB107 - Computability and complexity

Course Enrolment Limitations

The course is only offered to the students of the study fields the course is directly associated with.

fields of study / plans the course is directly associated with

there are 6 fields of study the course is directly associated with, display

Course objectives

The purpose of this course is to introduce computer science students to advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods of their applications.

Syllabus

• Methods of syntactic analyses of detCFLs.
• LL(k) grammars and languages, properties and analyzers.
• LR(k) grammars and languages, properties and analyzers.
• Relationships between LL, LR and detCFL.
• Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
• Automata and infinite words: infinite words, regular (rational) sets of infinite words.
• Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.

Literature

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
• Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. ISBN 3540614869. info
• SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
• CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info

Assessment methods (in Czech)

Během semestru jedna pisemná zkouška. Závěrečná zkouška je rovněž písemná; obě bez použití materiálů.

Language of instruction

Czech

Follow-Up Courses

• IA040 Modal and Temporal Logics for Processes
• IA041 Concurrency Theory
• PA008 Compiler Construction

Further Comments

The course is taught annually.

Teacher's information

http://www.fi.muni.cz/usr/kretinsky/fja2.html

• Enrolment Statistics (recent)