Accession Number : AD0708528

Title :   ALGEBRAIC METHODS IN AUTOMATA THEORY. PART I AND PART II.

Descriptive Note : Final scientific rept. 15 Mar 66-31 Aug 69,

Corporate Author : ASSOCIATION POUR L'ETUDE ET LA RECHERCHE EN TRAITEMENT DE L'INFORMATION PARIS (FRANCE)

Personal Author(s) : Schutzenberger,Marco P. ; Nivat,Maurice P.

Report Date : SEP 1969

Pagination or Media Count : 13

Abstract : The report summarizes research on algebraic tools that have applicability to automata and language theory. The problem of determining the structure of two words generating a free submonoid (i.e., that are not linked by any algebraic relation) was solved. The conjecture of Gilbert and Moore on the existence of a non-prefix finite complete code with bounded delay (in the theory of variable length codes) was proved. The structure of rational (i.e., regular) sets in finitely generated commutative monoids has been described. A mathematical framework was developed for the description of the rational subsets of the cartesian product of two free monoids. Several generalizations of standard theorems in the theory of algebraic languages and power series have been stated in concise algebraic form. A subclass of languages was identified for which an attempt was made to prove the decidability of the equivalence problem; a construction was developed that relates images of the Dyck set in an inverse homomorphism to some special types of Thue congruence on a free monoid. An analysis of sets and co-sets of algebraic languages showed that there exists a language which has just one grammar up to trivial changes. A notion of 'constellation' is being developed that permits the transformation of many graph theoretic and combinatorial problems into problems about algebraic languages or power series in non-commuting variables.

Descriptors :   (*ARTIFICIAL INTELLIGENCE, ALGEBRA), MONOIDS, LINGUISTICS, COMBINATORIAL ANALYSIS, CODING, SET THEORY, GRAPHICS, POWER SERIES, MATHEMATICAL MODELS, FRANCE

Subject Categories : Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE