Automata in Semi-rings

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

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

Registered students: 12
OrientationAttendance TypeSemesterYearECTS
THEŌRĪTIKĪ PLĪROFORIKĪ KAI THEŌRIA SYSTĪMATŌN KAI ELEGCΗOUCore Courses1110
Class Information
Academic Year2025 – 2026
Class PeriodWinter
Faculty Instructors
Weekly Hours3
Total Hours39
Class ID
600290409
Type Of Offer
  • Disciplinary Course
Course Type 2021
Specialization / Direction
Course Type 2011-2015
Knowledge Deepening / Consolidation
Mode of Delivery
  • Face to face
  • Distance learning
Digital Course Content
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
Prerequisites
General Prerequisites
Automata theory
Learning Outcomes
Upon successful completion of the course, the students will: 1. know the basic theory of semirings and especially the ones encountered in applications 2. know the properties of formal power series 3. know weighted automata over semrings, and be able to compute their behaviors and prove the closure properties of those behaviors with formal power series operations 4. be able to prove decidability results for weighted automata
General Competences
  • Apply knowledge in practice
  • Retrieve, analyse and synthesise data and information, with the use of necessary technologies
  • 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)
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
  • Multimedia
  • Book
Use of Information and Communication Technologies
Use of ICT
  • Use of ICT in Course Teaching
  • Use of ICT in Communication with Students
  • Use of ICT in Student Assessment
Description
Use of Maude program for weighted automata simulations. Online exercises' hours.
Course Organization
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures391.3✓
Reading Assigment1836.1✓
Tutorial130.4
Project200.7✓
Written assigments401.3✓
Exams50.2✓
Total30010
Student Assessment
Description
The final grade will be computed as follows: 1. Project 40% 2. Final written exams 60%
Student Assessment methods
  • Written Exam with Short Answer Questions (Formative, Summative)
  • Written Exam with Extended Answer Questions (Formative, Summative)
  • Written Assignment (Formative, Summative)
  • Performance / Staging (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
Σημειώσεις του διδάσκοντα
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-05-2025