IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2024
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2023
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2022
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2021
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2020
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2019
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2018
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2017
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2016
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2015
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2014
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2013
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2012
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2011
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2010
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2009
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2008
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2007
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2006
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
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2005
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
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2004, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2004
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
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2003, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2003
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
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
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2002, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.

IA006 Selected topics on automata theory

Faculty of Informatics
Autumn 2002
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
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja2.html
The course is also listed under the following terms Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (recent)