Module also offered within study programmes:
General information:
Annual:
2017/2018
Code:
AMA-2-079-MZ-s
Name:
Combinatorics on words
Faculty of:
Applied Mathematics
Study level:
Second-cycle studies
Specialty:
Matematyka w zarządzaniu
Field of study:
Mathematics
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polski i Angielski
Form and type of study:
Full-time studies
Course homepage:
 
Responsible teacher:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
Academic teachers:
dr hab. Foryś Wit (foryswit@wms.mat.agh.edu.pl)
dr Foryś Magdalena (maforys@agh.edu.pl)
Module summary

Kombinatoryka na słowach.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Potrafi samodzielnie i zespołowo pracować nad projektem MA2A_K03 Examination,
Activity during classes
M_K002 Potrafi samodzielnie wykorzystać znalezioną przez siebie literaturę MA2A_K06 Examination,
Activity during classes
Skills
M_U001 Potrafi samodzielnie wykorzystać metody generowania słów okresowych i słów bez powtórzeń MA2A_W08, MA2A_U16, MA2A_W07 Examination,
Activity during classes
M_U002 Potrafi rozwiązać proste równanie na słowach MA2A_W10, MA2A_U06, MA2A_W09, MA2A_W08, MA2A_W07, MA2A_U20 Test,
Essay,
Examination,
Activity during classes
Knowledge
M_W001 Zna podstawowe pojęcia i problemy kombinatoryki na słowach MA2A_W10, MA2A_W09, MA2A_W08, MA2A_U16, MA2A_W07 Examination,
Activity during classes
M_W002 Zna problematykę słów bez powtórzeń, w szczególności kombinatoryczne własności słowa Thue-Morse’a i możliwości zastosowań MA2A_W10, MA2A_W09, MA2A_W08, MA2A_W07 Examination,
Activity during classes
M_W003 Zna problematykę słów okresowych, homomorfizmów generujących takie słowa i ich zastosowania MA2A_W10, MA2A_W09, MA2A_W08, MA2A_U13, MA2A_W07, MA2A_U11 Examination,
Activity during classes
M_W004 Zna podstawowe problemy wymiaru i ich zastosowania w kodowaniu MA2A_W10, MA2A_U06, MA2A_W09, MA2A_W08, MA2A_U16, MA2A_W07, MA2A_U18 Examination,
Activity during classes
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Potrafi samodzielnie i zespołowo pracować nad projektem + + - - - - - - - - -
M_K002 Potrafi samodzielnie wykorzystać znalezioną przez siebie literaturę + + - - - - - - - - -
Skills
M_U001 Potrafi samodzielnie wykorzystać metody generowania słów okresowych i słów bez powtórzeń + + - - - - - - - - -
M_U002 Potrafi rozwiązać proste równanie na słowach + + - - - - - - - - -
Knowledge
M_W001 Zna podstawowe pojęcia i problemy kombinatoryki na słowach + + - - - - - - - - -
M_W002 Zna problematykę słów bez powtórzeń, w szczególności kombinatoryczne własności słowa Thue-Morse’a i możliwości zastosowań + + - - - - - - - - -
M_W003 Zna problematykę słów okresowych, homomorfizmów generujących takie słowa i ich zastosowania + + - - - - - - - - -
M_W004 Zna podstawowe problemy wymiaru i ich zastosowania w kodowaniu + + - - - - - - - - -
Module content
Lectures:
  1. PL

    1. Wolne półgrupy i monoidy, słowa, podpółgrupy i podmonoidy,

    2. Wkw na wolny podmonoid, kodowanie – zastosowania

    3. Sprzężenie, szeregi formalne słów

    4. słowa bez kwadratu, słowa nieskończone bez powtórzeń – zastosowania

    5. Słowo Thue-Morse’a; własności kombinatoryczne i inne – zastosowania

    6. Homomorfizmy wolnych monoidów, iteracje, powtarzalność

    7. Słowa okresowe, własności związane z okresowością – zastosowania

    8. Problemy wymiaru – twierdzenie o defekcie – zastosowanie w problemach kodowania

    9. Równania na słowach

    10. Twierdzenie o faktoryzacji (M.P.Schutzenberger)

  2. EN

    Combinatorics on words is a field that has grown separately within several branches of mathematics – for example finite group and/or semigroup theory, probability theory. It appears very frequently in theoretical computer science, especially dealing with formal languages, grammars and automata theory. The lecture is an attempt to present a unified treatment of the theory of combinatorics on words.

    1. Free semigroups and free monoids, words; subsemigroups and submonoids

    2. Free submonoids (subsemigroups); coding – applications

    3. Conjugacy; formal series of words

    4. square-free words, Infinite words with no repetition – applications

    5. Infinite Thue-Morse word; combinatorial properties – applications

    6. Morphisms of free monoids; iteration of a morphism; repetitive morphisms

    7. Periodic words, properties connected with periodicity – applications

    8. Dimension problem – Defect Theorem – application in coding problems

    9. Equations on words

    10. Critical Factorization Theorem (M.P.Schutzenberger)

Auditorium classes:
-//-
Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 150 h
Module ECTS credits 6 ECTS
Participation in auditorium classes 30 h
Participation in lectures 30 h
Preparation for classes 30 h
Realization of independently performed tasks 46 h
Contact hours 10 h
Examination or Final test 4 h
Additional information
Method of calculating the final grade:

Ocena końcowa (OK) jest oceną biorącą pod uwagę ocenę z ćwiczeń i egzaminu pisemnego

Prerequisites and additional requirements:

licencjat

Recommended literature and teaching resources:

1. M. Lothaire, Combinatorics on words,Cambridge Univ.Press, 1997
2. J.Karhumaki, Combinatorics on words, Univ.Turku, preprint, 2015

Scientific publications of module course instructors related to the topic of the module:

• W.Foryś, Asymptotic behaviour of bi-infinite words, RAIRO – Theoretical Informatics and Applications, 38, 2004,pp. 27-48

• W.Foryś, T.Krawczyk, An algorithmic approach to the problem of a semiretract base, Theoretical Computer Science, vol.369, 2006, pp.314-322

• W.Foryś, Retractions and retracts of free topological monoids, Intern.J. Comp. Mathematics vol.83, 2006 pp. 21-26

• M. Foryś,On the Growth Rate of Words in Generalized Thue-Morse Sequence, Int. J. Comp. Math., 91(8) (2014), 1627-1634

• M. Foryś,On sequence entropy of Thue-Morse shift, Schedae Inf., Vol.22, pp.19-25, 2013

Additional information:

Przedmiot może być prowadzony w języku angielskim.