# Matematica | FREE SEMIGROUPS AND THEORY OF CODES

## Matematica FREE SEMIGROUPS AND THEORY OF CODES

 0512300027 DIPARTIMENTO DI MATEMATICA EQF6 MATHEMATICS 2016/2017

 YEAR OF COURSE 3 YEAR OF DIDACTIC SYSTEM 2010 PRIMO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY MAT/02 6 48 LESSONS SUPPLEMENTARY COMPULSORY SUBJECTS
 COSTANTINO DELIZIA T
Objectives
1.KNOWLEDGE AND UNDERSTANDING: THIS COURSE WILL PROVIDE AN INTRODUCTION TO THE THEORY OF FREE SEMIGROUPS AND MONOID AND TO THE THEORY OF CODES, WITH EMPHASYS ON PROPERTIES OF WORDS ON AN ALPHABET.
2.APPLYING KNOWLEDGE AND UNDERSTANDING: COURSE AIM IS ALSO TO ENABLE STUDENTS TO SOLVE MANY KINDS OF PROBLEMS APPLYING THE ACQUIRED THEORETICAL KNOWLEDGE.
Prerequisites
TO BETTER UNDERSTAND THE TOPICS OF THIS COURSE, IT IS ADVISABLE TO HAVE STUDIED ALGEBRA 1.
Contents
SEMIGROUPS AND MONOIDS. THE GENERAL ASSOCIATIVITY THEOREM. THE GROUP OF UNITS OF A MONOID. ZERO ELEMENT OF A SEMIGROUP. IDEMPOTENT ELEMENTS. FACTORS OF A ELEMENT OF A SEMIGROUP. REGULAR SEMIGROUPS. COMMUTATIVE SEMIGROUPS. THE SEMIGROUP OF SUBSETS OF A SEMIGROUP. DIRECT PRODUCTS. WORD SEMIGROUPS AND MONOID. THE MONOID OF BINARY RELATIONS ON A SET. MONOIDS OF TRANSFORMATIONS. MONOIDS OF PARTIAL FUNCTIONS. SUBSEMIGROUPS AND SUBMONOIDS. SUBSEMIGROUPS AND SUBMONOIDS GENERATED BY A SUBSET. FNITELY GENERATED SEMIGROUPS. MONOGENIC SEMIGROUPS. THE ORDER OF A ELEMENT. THE INDEX AND THE PERIOD OF A ELEMENT OF FINITE ORDER. PERIODIC SEMIGROUPS. OMOMORPHISMS OF SEMIGROUPS AND MONOIDS. EMBEDDING OF A DENUMERABLY GENERATED SEMIGROUP IN A 2-GENERATED ONE. CONGRUENCES OF A SEMIGROUP. QUOTIENTS. HOMOMORPHISM THEOREMS. IDEALS. IDEALS GENERATED BY A SUBSET. REES CONGRUENCES AND REES QUOTIENTS. SEMIGROUPS OF FACTORS. SYNTACTIC CONGRUENCES. SYNTACTIC SEMIGROUPS. SEMIRINGS. THE LATTICE OF CONGRUENCES OF A SEMIGROUP. THE CONGRUENCE GENERATED BY A RELATION IN A SEMIGROUP. FREE SEMIGROUPS AND MONOIDS. LINERALY INDEPENDENT SETS AND BASIS. UNIQUENESS OF THE BASE. UNIVERSAL PROPERTY OF SEMIGROUPS AND MONOIDS. EXISTENCE AND UNIQUENESS UP TO ISOMORPHISMS OF FREE SEMIGROUP AND MONID WITH BASE OF GIVEN CARDINALITY. LENGHT OF A ELEMENT IN A FREE MONOID. LEVI LEMMA. LYNDON-SCHUTZENBEGER LEMMA. SUBMONOIDS OF FREE MONOIDS. IRRIDUCIBLE ELEMENTS. CHARACTERIZATIONS OF FREE SUBMONOIDS OF FREE MONOIDS. SCHUTZENBEGER THEROEM. UNITARY AND BIUNITARY SUBMONOIDS OF WORD MONOIDS. THE FREE HALL. THE DEFECT THEOREM. PRESENTATIONS OF SEMIGROUPS AND MONOIDS. THE FREE COMMUTATIVE MONOID. THE BICYCLIC MONOID. WORDS. LENGHT AND FACTORS OF A WORD. PREFIXES AND SUFFIXES. SUBWORDS AND THEIR MULTIPLICITY. REVERSED WORDS. PALINDROME WORDS. CONJUGATED WORDS. PERMUTABLE WORDS. PRIMITIVE WORDS. EXISTENCE AND UNIQUENESS OF THE ROOT OF A NON-EMPTY WORD. ORDERS IN FREE MONOIDS. CODES. CHARACTERIZATIONS OF CODES. UNIFORM CODES. ORDER 2 CODES. PREFIX, SUFFIX, BIFIX CODES AND THEIR CHARACTERIZATIONS. THE SARDINAS-PATTERSON THEOREM. BERNOULLI DISTRIBUTIONS ON AN ALPHABET AND MEASURES. THE KRAFT-MCMILLAN INEQUALITY. MAXIMAL CODES. DENSE SETS OF WORDS. COMPLETE SETS OF WORDS. COMPLETENESS OF A MAXIMAL CODE. MAXIMALITY OF A NON-DENSE COMPLETE CODE. PREFIX MAXIMAL CODES AND THEIR CHARACTERIZATIONS.
SYNCHRONIZING CODES. BINARY UNIFORM CODES: MAXIMUM LIKELIHOOD DECODING, HAMMING DISTANCE, ERROR-DETECTING CODES, ERROR-CORRECTING CODES.
Teaching Methods
THIS COURSE CONSISTS OF THEORETICAL LESSONS, DURING WHICH WILL ALSO BE SHOWN HOW THE GAINED KNOWLEDGE CAN BE USED FOR THE SOLUTION OF PROBLEMS RELATED TO THE ADDRESSED ISSUES.
Verification of learning
EXAM IS AN ORAL TEST, DURING WHICH WILL BE EVALUED THE KNOWLEDGE OF TOPICS COVERED IN CLASS THEORY BUT ALSO THE CAPACITY TO USE THEM TO SOLVE PROBLEMS OF ELEMENTARY TYPE.
Texts
A.DE LUCA, F.D'ALESSANDRO, TEORIA DEGLI AUTOMI FINITI, SPRINGER, MILANO, 2013.