Algebraic theory of automata and languages / Masami Ito.

Format:

Book

Author/Creator:

Itō, Masami, 1941-

Contributor:

John G. Hartman Memorial Library Fund.

Language:

English

Subjects (All):

Formal languages.

Machine theory.

Physical Description:

x, 199 pages : illustrations ; 24 cm

Place of Publication:

River Edge, N.J. : World Scientific, [2004]

Summary:

The theory of formal languages and the theory of automata were both initiated in the late 1950s, explains Ito (Kyoto Sangyo U., Japan), and the two fields have since developed into important theoretical foundations of computer science. He looks at the two from the algebraic perspective, beginning with the algebraic structure of automata, and partially ordered sets of automata as a kind of global theory. Then he delves into grammars, languages, and operations on languages. To conclude, he introduces directable automata as a special case. Annotation ©2004 Book News, Inc., Portland, OR (booknews.com)

Contents:

1 Group-Matrix Type Automata 5

1.1 Strongly connected automata 6

1.2 Group-matrix type automata 9

1.3 Representations of automata 19

1.4 Equivalence of regular systems 22

1.5 Characteristic monoids and input sets 30

1.6 Direct product of automata 35

1.7 Factor automata 38

1.8 Prime order case 41

1.9 Regularities 43

1.10 Application to factor automata 46

1.11 Application to direct products 47

2 General Automata 51

2.1 Generalized representations 51

2.2 Some properties 54

2.3 Representations of general automata 57

2.4 Regularities 61

3 Classes of Automata as Posets 63

3.1 Introductory notions and results 63

3.2 Classes of automata 65

3.3 Classes which do not form lattices 69

3.4 Classes which form lattices 71

3.5 Computation of [A * B superscript V(P)] 76

4 Languages and Operations 83

4.1 Grammars and acceptors 83

4.2 Operations on languages 93

4.3 Shuffle products and n-insertions 94

4.4 Decompositions 96

4.5 Equations on languages 99

4.6 Shuffle closures 102

5 Shuffle Closed Languages 113

5.1 Sh-closed and ssh-closed languages 113

5.2 Sh-free languages and sh-bases 114

5.3 Commutative regular languages 117

5.4 Regular ssh-closed languages 122

5.5 Hypercodes 124

6 Insertions and Deletions 127

6.1 Insertion closures 127

6.2 Deletion closures 130

6.3 Ins-closed and del-closed languages 135

6.4 Combination of operations 137

7 Shuffles and Scattered Deletions 141

7.1 Shuffle residuals and closures 141

7.2 Maximal shuffle residuals 145

7.3 Scattered deletion closure 151

8 Directable Automata 157

8.1 Deterministic case 158

8.2 Nondeterministic case 162

8.3 Classes of regular languages 164

8.4 Commutative case 181.

Notes:

Includes bibliographical references and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the John G. Hartman Memorial Library Fund.

ISBN:

9810247273

OCLC:

55681595