Automata in Semi-rings

Course Information
TitleΑΥΤΟΜΑΤΑ ΣΕ ΗΜΙΔΑΚΤΥΛΙΟΥΣ / Automata in Semi-rings
Code0865
FacultySciences
SchoolMathematics
Cycle / Level2nd / Postgraduate
Teaching PeriodSpring
CoordinatorGeorgios Rachonis
CommonNo
StatusActive
Course ID600000888

Programme of Study: PMS Tmīmatos Mathīmatikṓn (2018-sīmera)

Registered students: 14
OrientationAttendance TypeSemesterYearECTS
THEŌRĪTIKĪ PLĪROFORIKĪ KAI THEŌRIA SYSTĪMATŌN KAI ELEGCΗOUCore Courses2110
STATISTIKĪ KAI MONTELOPOIĪSĪCompulsory Course2110

Class Information
Academic Year2019 – 2020
Class PeriodSpring
Faculty Instructors
Weekly Hours3
Class ID
600148308
Course Category
Knowledge Deepening / Consolidation
Language of Instruction
  • Greek (Instruction, Examination)
  • English (Instruction, Examination)
Learning Outcomes
The course focuses on the study of weighted automata over a commutative semiring K, its behavior as well as the properties of the class of the behaviors of all such weighted automata over K. Students will understand the main differences on proof techniques among finite automata and weighted automata over K. Furthermore, students will understand the differences among finite and weighted automata with reference to determinization and decidability properties.
General Competences
  • Apply knowledge in practice
  • Make decisions
  • Work in an international context
  • Work in an interdisciplinary team
  • Generate new research ideas
Course Content (Syllabus)
Semirings. Weighted automata over semirings. Recognizable series. Properties of recognizable series. The determinization problem for weighted automata over semirings. Decidability problems. Applications: Fuzzy languages. Digital image compression.
Keywords
Seimirings, weighted automata, series
Educational Material Types
  • Notes
Course Organization
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures30010
Total30010
Student Assessment
Description
Written exams
Student Assessment methods
  • Written Exam with Short Answer Questions (Summative)
  • Written Exam with Extended Answer Questions (Formative)
  • Written Exam with Problem Solving (Formative)
Bibliography
Additional bibliography for study
- M. Droste, W. Kuich, and H. Vogler, eds., Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer, 2009. - Z. Ésik, W. Kuich, Modern Automata Theory, http://www.dmg.tuwien.ac.at/kuich/mat.ps - W. Kuich, Semirings and formal power series: Their relevance to formal languages and automata theory, in: Handbook of of Formal Languages, volume 1, Chapter 9, Springer, Berlin, pages 609-667. - W. Kuich A. Salomaa, Semirings, Automata, Languages, EATCS Monographs in Theoretical Computer Science, Springer, 1986. - J. Sakarovitch, Elements of Automata Theory, Cambridge, 2009. - A. Salomaa, M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer, Berlin, 1978. - J. Berstel, Ch. Reutenauer, Rational Series and Their Languages, EATCS Monographs in Theoretical Computer Science, Springer, 1988.
Last Update
07-02-2020