Weighted automata

General data

Course ID:	1000-2M22AW
Erasmus code / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration The ISCED (International Standard Classification of Education) code has been designed by UNESCO.
Course title:	Weighted automata
Name in Polish:	Automaty ważone
Organizational unit:	Faculty of Mathematics, Informatics, and Mechanics
Course groups:	(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science
ECTS credit allocation (and other scores):	(not available) Basic information on ECTS credits allocation principles: the annual hourly workload of the student’s work required to achieve the expected learning outcomes for a given stage is 1500-1800h, corresponding to 60 ECTS; the student’s weekly hourly workload is 45 h; 1 ECTS point corresponds to 25-30 hours of student work needed to achieve the assumed learning outcomes; weekly student workload necessary to achieve the assumed learning outcomes allows to obtain 1.5 ECTS; work required to pass the course, which has been assigned 3 ECTS, constitutes 10% of the semester student load. view allocation of credits
Language:	English
Main fields of studies for MISMaP:	computer science
Type of course:	elective monographs
Requirements:	Languages, automata and computations 1000-214bJAO
Prerequisites:	Computational complexity 1000-218bZO
Short description:	(in Polish) Najważniejsze twierdzenia dotyczące tematyki automatów ważonych. Przykłady zastosowań w innych dziedzinach.
Full description:	1. Introduction, weighted automata as a generalisation of finite automata or as a generalisation of linear recursive sequences. Several semirings for which such automata are defined. 2. Schützenberger’s theorem about decidability of equivalence over fields. Learning weighted automata. 3. Probabilistic automata 4. Subclasses defined according to the number of runs in the automaton. Weber and Seidl characterisation. 5. Linear recursive sequences: Skolem-Mahler-Lech theorem and NP-hardness of the Skolem problem. 6. Undecidability of most of the problems for weighted automata. 7. Hashiguchi’s theorem on decidability of the boundedness problem over the min-plus semiring. 8. Decidability of the finiteness problem with elementary bounds. 9. The determinisation problem, decidability for unambiguous automata. 10. Nonlinear weighted automata.
Learning outcomes:	(in Polish) Wiedza Student pogłębia wiedzę o klasycznych zastosowaniach teorii automatów ważonych. Umiejętności Student umie rozpoznać granice obliczalności różnych wariantów modeli. Student potrafi modelować różne problemy za pomocą odpowiednich automatów. Kompetencje Student rozumie narzędzia matematyczne wypracowane we współczesnej teorii automatów i potrafi z nich korzystać zarówno w samej informatyce, jak i w jej zastosowaniach
Assessment methods and assessment criteria:	(in Polish) Prace domowe i egzamin.

This course is not currently offered.

Course descriptions are protected by copyright.
Copyright by University of Warsaw.