Theoritical Informatics II

Course Information
TitleΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ ΙΙ / Theoritical Informatics II
Code0432
FacultySciences
SchoolMathematics
Cycle / Level1st / Undergraduate
Teaching PeriodSpring
CoordinatorGeorgios Rachonis
CommonYes
StatusActive
Course ID40000484

Programme of Study: Merikīs Foítīsīs (2014-sīmera)

Registered students: 5
OrientationAttendance TypeSemesterYearECTS
KORMOSElective Courses belonging to the selected specializationSpring-5.5

Programme of Study: UPS of School of Mathematics (2014-today)

Registered students: 187
OrientationAttendance TypeSemesterYearECTS
CoreElective Courses belonging to the selected specialization635.5
Class Information
Academic Year2025 – 2026
Class PeriodSpring
Faculty Instructors
Weekly Hours3
Total Hours39
Class ID
600276388
Course Type 2016-2020
  • Background
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
Digital Course Content
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
Prerequisites
Required Courses
  • 0401 Theoretical Informatics I
General Prerequisites
Knowledge and ability to handle basic concepts of finite automata, MSO logic, FO logic, and LTL.Despription of applications on model checking.
Learning Outcomes
Upon successful completion of the course, students will be able to:      Understand the closure of the class of recognizable languages under homomorphisms. To understand the main concepts of MSO logic, FO logi and LTL. They will be able to understand an dprove the expressive equivalenc of finite automata and MSO logic. They will be also able to show the expressive equivalence of FO logic and LTL. Moreover, they will be able to present simple examples of the application of LTL to model checking.
General Competences
  • Apply knowledge in practice
  • Retrieve, analyse and synthesise data and information, with the use of necessary technologies
  • Adapt to new situations
  • Make decisions
  • Work autonomously
  • Work in teams
  • Work in an international context
  • Work in an interdisciplinary team
  • Generate new research ideas
  • Be critical and self-critical
  • Advance free, creative and causative thinking
Course Content (Syllabus)
Closure properties of the class of recpgnizable languages under homomorphisms. Monadic second-order (MSO) logic. Expressive equivalence of finite automata and MSO logic. First-order (FO) logic. Linear temporal logic (LTL). Expressive equivalence of FO and LTL. Application of LTL to model checking.
Keywords
Finite automata, MSO logic, FO logic, LTL.
Educational Material Types
  • Notes
  • Book
Course Organization
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures39✓✓
Reading Assigment123
Exams3
Total165
Student Assessment
Student Assessment methods
  • Written Exam with Multiple Choice Questions (Summative)
  • Oral Exams (Formative)
  • Written Exam with Problem Solving (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού, H.Lewis, Χ.Παπαδημητρίου, Κριτική, 2005, Αθήνα. - Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Παν/κές Εκδόσεις Κρήτης, 2007 έδοση 2009.
Additional bibliography for study
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 3rd edition 2007. - Juraj Hromkovic, Theoretical Computer Science, Texts in Theoretical Computer Science, EATCS Series, Springer, 2004. - Harry Lewis, Christos Papadimitriou, Elements of the Theory of Computation, Prentice-Hall Inc., 2nd edition 1998. - Grzegorz Rozenberg, Arto Salomaa eds., Handbook of Formal Languages, volumes 1-3, Springer-Verlag, Berlin, 1997.
Last Update
24-01-2024