內容大鋼
By combinatorial semigroups, we mean a general term of concepts, facts and methods which are produced in investigating of algebraic and combinatorial properties, constructions, classifications and interrelations of formal languages and automata, codes, finite and infinite words by using semigroup theory and combinatorial analysis. The main research objects in this field are the elements and subsets of the free semigroups and monoids and many combinatorial properties of these objects, which are closely related to the algebraic theory of semigroups.
This book first introduces some basic concepts and notations in combinatorial semigroups. Since many contents involving the constructions of (generalized) disj tractive languages and regular languages are closely related to the algebraic theory of codes, some selected topics are introduced in the following chapter, including the method of defining codes by using dependence systems, the maximality and completeness of codes, and the detailed discussion of some special kinds of codes such as convex codes, semaphore codes and solid codes. Then the remaining chapters present the main topics of the book-regular languages, disjunctive languages, and their various kinds of generalizations.
This book might be useful to researchers in mathematics who are interested in combinatorial semigroups.
目錄
1 Basic Concepts and Notations
1.1 Semigroups (Monoids)
1.2 Free Semigroups (Monoids) and Languages
1.3 Disjunctive (Regular) and Dense Subsets of Semigroups
1.4 Periods and Primitive Words
1.5 Infinite Words
2 Some Common-Used Codes
2.1 Methods for Defining Codes
2.2 Maximal Codes and Complete Codes
2.3 Convex Codes
2.4 Semaphore Codes
2.5 Solid Codes
2.6 Congruences Coming From Solid Codes
3 Regular Languages
3.1 Automata
3.2 Recognizability of Regular Languages
3.3 Rationality of Regular Languages
3.4 A Decomposition of Regular Languages
3.5 Restricted Burnside Problem and Regular Languages
4 Disjunctive Languages
4.1 Disjunctive Languages Over One-Letter Alphabets
4.2 Disjunctive Languages and Dense Languages
4.3 Disjunctive Domains
4.4 Infinite Disjunctive Decompositions of Dense Languages
4.4.1 Disjunctive Splittability of Dense Languages
4.4.2 DP-Splittability
4.4.3 Semi-DP-Splittability
4.5 Finite Disjunctive Decompositions of Dense Languages
4.6 A Constructing Method of Decomposition Components
5 F-Disjunctive Languages
5.1 F-Disjunctive Languages
5.1.1 Definition， Elementary Properties and Examples
5.1.2 F-Disjunctive Pairs
5.1.3 Operations on F-Disjunctive Languages
5.1.4 Special Classes of F-Disjunctive Languages
5.2 F-Disjunctive Domains
5.2.1 Examples and Basic Properties
5.2.2 On the Uniform Density of F-Disjunctive Domains
5.3 Syntactic Semigroups of F-Disjunctive Languages
5.3.1 Semigroups with I-Quasi Length
5.3.2 Syntactic I-Ql-Semigroups
5.3.3 Ql-Semigroups and Free Semigroups
5.3.4 I-Ql-Monoids
6 Relatively Disjunctive Languages and Relatively Regular Languages
6.1 Relatively Disjunctive Languages
6.2 Relatively Regular Languages
6.3 The Hierarchies of Relatively Disjunctive Languages (I)
6.4 The Hierarchies of Relatively Disjunctive Languages (II)
7 Generalized Disjunctive Languages
7.1 Language Classes and Monoid Classes
7.2 Quasi-Disjunctive Languages
7.2.1 Quasi-Disjunctivity and Auto-disjunctivity
7.2.2 Regular Quasi-Disjunctive and Auto-disjunctive Languages
7.3 Qf-Disjunctive Languages
7.3.1 Definitions and Elementary Properties
7.3.2 Operations on Qf-Disjunctive Languages
7.3.3 Qf-Disjunctive Languages and Infix Codes
7.4 C-Disjunctive Languages
7.5 Generalized Disjunctive Hierarchy
8 PS-Regular Languages
8.1 Permissible Sets and Prefix-Suffix-Sets
8.2 Some Characterizations of -Regular Languages and Regular Languages
8.3 On the Class of PS-Regular Languages
8.4 Conclusions
References
Index
[