2. Matematica
  3. Teaching
  4. Course Units

FREE SEMIGROUPS AND THEORY OF CODES

Matematica FREE SEMIGROUPS AND THEORY OF CODES

0512300027
DIPARTIMENTO DI MATEMATICA
MATHEMATICS
2013/2014



YEAR OF COURSE 3
YEAR OF DIDACTIC SYSTEM 2010
SECONDO 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. COMMUTATIVE SEMIGROUPS. IDENTITY ELEMENT AND ZERO. IDEMPOTENT ELEMENTS. MONOIDS. MINIMUM MONOID CONTAINING A GIVEN SEMIGROUP. MINIMUM SEMIGROUP WITH ZERO CONTAINING A GIVEN SEMIGROUP. GROUPS. SUBSEMIGROUPS. SUBSEMIGROUP GENERATED BY A SUBSET. MINIMUM SUBSEMIGROUP CONTAINING A GIVEN SEMIGROUP WITH ZERO. GLOBAL SEMIGROUP. IDEALS. CANCELLATIVE SEMIGROUPS. PRODUCT OF SEMIGROUPS. HOMOMORPHISMS OF SEMIGROUPS AND THEIR PROPERTIES. THE MONOID OF ENDOMORPHISMS OF A SEMIGROUP. THE AUTOMORPHISM GROUP OF A SEMIGROUP. EMBEDDING OF A SEMIGROUP IN A SEMIGROUP OF TRANSFORMATIONS. MONOGENIC SEMIGROUPS. ORDER OF AN ELEMENT. INDEX AND PERIOD OF AN ELEMENT OF FINITE ORDER. PERIODIC SEMIGROUPS. EXISTENCE OF SEMIGROUPS WITHOUT IDEMPOTENTS. CORRESPONDENCE BETWEEN COMMUTATIVE SEMIGROUPS OF IDEMPOTENTS AND SEMILATTICES. THE SEMIGROUP OF RELATIONS IN A SET. TRANSITIVE CLOSURE OF A RELATION. EQUIVALENCE RELATION GENERATED BY A RELATION. SEMIGROUP CONGRUENCES AND QUOTIENT. HOMOMORPHISM THEOREMS FOR SEMIGROUPS. SYNTACTIC CONGRUENCES. REES CONGRUENCES. REES HOMOMORPHISMS. THE SEMIGROUP OF WORDS OVER AN ALPHABET. THE MONOID OF WORDS OVER AN ALPHABET. FREE SEMIGROUPS: UNIQUENESS OF THE BASE, UNIVERSAL PROPERTY, UNIQUENESS UP TO ISOMORPHISM OF THE FREE SEMIGROUP WITH BASE OF FIXED CARDINALITY, EXISTENCE OF AN EPIMORPHISM OF ANY SEMIGROUP IN A SUITABLE FREE SEMIGROUP. COMMUTATIVE FREE SEMIGROUPS. CONGRUENCE GENERATED BY A RELATION IN A SEMIGROUP. PRESENTATIONS OF SEMIGROUPS. DERIVABLE WORDS. FINITELY PRESENTED SEMIGROUPS. EMBEDDING OF A COUNTABLY GENERATED SEMIGROUP IN A 2-GENERATED SEMIGROUP. SUBMONOIDS. HOMOMORPHISMS OF MONOIDS. SUBMONOID GENERATED BY A SUBSET. FREE MONOIDS: UNIQUENESS OF THE BASE, UNIVERSAL PROPERTY, UNIQUENESS UP TO ISOMORPHISM OF THE FREE MONOID WITH BASIS OF FIXED CARDINALITY, EXIXTENCE OF AN EPIMORPHISM OF ANY MONOID IN A SUITABLE FREE MONOID. PRESENTATIONS OF MONOIDS. THE BICYCLIC MONOID. THE GROUP OF INVERTIBLE ELEMENTS OF A MONOID. REGULAR MONOIDS. CONICAL MONOIDS. ATOMS. ATOMIC MONOIDS. FACTORS OF AN ELEMENT OF A MONOID. EQUIDIVISIBLE MONOIDS. RIGID MONOIDS. CONJUGATED WORDS. SUBMONOIDS OF A FREE MONOID. CHARACTERIZATION OF FREE SUBMONOIDS OF A MONOID OF WORDS OVER AN ALPHABET. FREE HULL OF A SUBSET OF THE FREE MONOID OF WORDS OVER AN ALPHABET. THE DEFECT THEOREM. PRIMITIVE WORDS. LANGUAGES. CODES. BLOCK CODES. PREFIXES. PREFIX ORDERING. THE SARDINAS AND PATTERSON ALGORITHM. SQUARE-FREE WORDS. INFINITE WORDS. THE THUE-MORSE INFINITE WORDS. UNITARY MONOIDS. PREFIX SETS, SUFFIX SETS, BIFIX SETS. PREFIX CODES, SUFFIX CODES, BIFIX CODES. CHARACTERIZATION OF PREFIX (SUFFIX, BIFIX) CODES AS BASES OF LEFT UNITARY (RIGHT UNITARY, UNITARY) SUBMONOIDS. CODING AND DECODING. CODES WITH LIMITED DELAY. BERNOULLI DISTRIBUTION ON A FINITE ALPHABET. MEASURES INDUCED BY A BERNOULLI DISTRIBUTION ON A FINITE ALPHABET. MEASURES OF A CODE AND THEIR PROPERTIES. MAC MILLAN INEQUALITY. KRAFT MAC-MILLAN INEQUALITY. MAXIMAL CODES. KRAFT THEOREM.
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. STUDENTS WILL ALSO BE ASKED TO DISCUSS ONE OF THE QUESTIONS PROPOSED DURING THE COURSE.
Texts
J.M. HOWIE, AN INTRODUCTION TO SEMIGROUP THEORY, ACADEMIC PRESS, LONDON, 1976 --- M. LOTHAIRE, COMBINATORICS ON WORDS, ADDISON-WESLEY, READING, 1983 --- J. BERSTEL AND D. PERRIN, THEORY OF CODES, ACADEMIC PRESS, LONDON, 1976.
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]