2. Professors
  3. Teaching

FREE SEMIGROUPS AND THEORY OF CODES

Costantino DELIZIA FREE SEMIGROUPS AND THEORY OF CODES

0512300027
DIPARTIMENTO DI MATEMATICA
MATHEMATICS
2014/2015



YEAR OF COURSE 3
YEAR OF DIDACTIC SYSTEM 2010
PRIMO SEMESTRE
CFUHOURSACTIVITY
648LESSONS
COSTANTINO DELIZIA T Curriculum
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 AIMS IS ALSO TO ENABLE STUDENTS TO SOLVE MANY KINDS OF PROBLEMS APPLYING THE ACQUIRED THEORETICAL KNOWLEDGE.
3.MAKING JUDGEMENTS: STUDENTS ARE GUIDED TO LEARN IN A CRITICAL AND RESPONSIBLE WAY WHAT IS EXPLAINED IN THEIR CLASS AND TO IMPROVE THEIR SKILLS ASSESSMENT THROUGH THE STUDY OF MATERIALS PROVIDED BY THE TEACHER.
4.COMMUNICATION SKILLS: AT THE END OF THE COURSE STUDENTS MUST BE ABLE TO FORMULATE PROPERLY DEFINITIONS AND THEOREMS CONCERNING THE CONTENTS OF THE COURSE, AND TO USE DEMONSTRATIVE TECHNIQUES.
5.LEARNING SKILLS: STUDENTS WILL GAIN KNOWLEDGE THAT MAKES IT POSSIBLE TO LEARN MORE ADVANCED MATHEMATICAL ARGUMENTS, POSSIBLY USED BY OTHER SCIENCES.
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
ORAL EXAMINATION.
Texts
A.DE LUCA, F.D'ALESSANDRO, TEORIA DEGLI AUTOMI FINITI, SPRINGER, MILANO, 2013.
More Information
MORE INFORMATION ABOUT THIS COURSE, INCLUDING THE PROGRAM IN MORE DETAILED VERSION, THE QUESTION PROPOSED DURING THE COURSE AND ALL DATES OF THE NEXT EXAMS CAN BE FOUND AT THE ADDRESS
HTTP://WWW.DIPMAT.UNISA.IT/PEOPLE/DELIZIA/WWW/SEMIGRUPPI.HTML
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2016-09-30]