AUTOMATA IN SEMIRINGS
| Title | ΑΥΤΟΜΑΤΑ ΣΕ ΗΜΙΔΑΚΤΥΛΙΟΥΣ / AUTOMATA IN SEMIRINGS |
| Code | ΣΜΥ024 |
| Faculty | Sciences |
| School | Mathematics |
| Cycle / Level | 2nd / Postgraduate |
| Teaching Period | Winter/Spring |
| Coordinator | Georgios Rachonis |
| Common | No |
| Status | Active |
| Course ID | 600025960 |
Programme of Study: PMS Tmīmatos Mathīmatikṓn (2025-2030)
Registered students: 0
| Orientation | Attendance Type | Semester | Year | ECTS |
|---|---|---|---|---|
| STATISTIKĪ, MONTELOPOIĪSĪ KAI YPOLOGISTIKES METHODOI | Elective Courses belonging to the selected specialization | Winter | - | 10 |
| Academic Year | 2025 – 2026 |
| Class Period | Winter |
| Faculty Instructors | |
| Weekly Hours | 3 |
| Total Hours | 39 |
| Class ID | 600268407
|
Course Type 2021
Specialization / Direction
Course Type 2011-2015
Knowledge Deepening / Consolidation
Mode of Delivery
- Face to face
Digital Course Content
- e-Study Guide https://qa.auth.gr/en/class/1/600268407
- Other: http://users.auth.gr/grahonis/AOS.html
Language of Instruction
- Greek (Instruction, Examination)
- English (Instruction, Examination)
Prerequisites
General Prerequisites
Knowledge of the undergraduate courses
Theoretical Computer Science I
Theoretical Computer Science II
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. Machine learning algorithms.
Keywords
Seimirings, weighted automata, series
Educational Material Types
- Notes
Course Organization
| Activities | Workload | ECTS | Individual | Teamwork | Erasmus |
|---|---|---|---|---|---|
| Lectures | 39 | ✓ | |||
| Reading Assigment | 258 | ✓ | |||
| Exams | 3 | ✓ | |||
| Total | 300 |
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
01-12-2024
