This volume consists of papers selected from the presentations at the workshop and includes mainly recent developments in the fields of formal languages, automata theory and algebraic systems related to the theoretical computer science and informatics. It covers the areas such as automata and grammars, languages and codes, combinatorics on words, cryptosystems, logics and trees, Grobner bases, minimal clones, zero-divisor graphs, fine convergence of functions, and others.
Author(s): Masami Ito
Publisher: World Scientific Publishing Company
Year: 2010
Language: English
Pages: 247
Tags: Математика;Дискретная математика;Теория конечных автоматов;
CONTENTS......Page 8
Preface......Page 6
1. Introduction......Page 10
2. Equivalent Strong Varieties of Partial Algebras......Page 16
3. Minimal Partial Clones......Page 20
4. Strongly Solidifyable Partial Clones......Page 21
References......Page 29
1. Introduction......Page 32
2. Preliminaries......Page 33
3. A Novel Cipher......Page 34
3.2. Encryption......Page 35
5.1. Automatic Learning Algorithms......Page 36
5.2. Adaptive Chosen-Ciphertext Attack, Adaptive Chosen- -Plaintext Attack, Adaptive Chosen-Plaintext -Chosen- -Ciphertext Attack......Page 37
7. Conclusion......Page 38
References......Page 39
1. Linear languages......Page 42
2. -monoids......Page 44
3. Completely idempotent semiring-semimodule pairs......Page 47
4. Conway semiring-semimodule pairs......Page 50
5. Automata......Page 52
6. Operational characterization of linear languages......Page 53
References......Page 55
1. Introduction......Page 56
2. Trees......Page 57
3. Temporal logics......Page 59
4. The correspondence......Page 61
5. Algebraic characterization......Page 63
6. Ehrenfeucht-Fraısse type games......Page 65
References......Page 70
1. Introduction......Page 72
2. Results......Page 73
References......Page 78
1. Introduction......Page 80
2. Preliminaries and formalism for language descriptions......Page 82
3. Matrix algorithm and size estimation of languages......Page 85
4. Partition of the derivations and size estimation of languages......Page 89
5. Conclusion......Page 92
References......Page 93
1. Well-ordered reexive semigroups......Page 94
2. Factors and appearances......Page 98
3. Rewriting on algebras......Page 101
4. Grobner bases on algebras......Page 105
5. Critical pair theorem......Page 107
References......Page 111
1. Introduction......Page 112
2. Definitions......Page 114
3. Normal Forms......Page 117
4. Relations to Other Language Classes......Page 118
5. Characterization and Decidability Results......Page 119
6. Closure Properties......Page 120
References......Page 121
1. Introduction......Page 122
2. Definitions......Page 123
3. A Hierarchy of Finitely Expandable Deep PDAs......Page 125
References......Page 132
1. Introduction......Page 134
2. Basic definitions and relationships......Page 135
3. The distance to primitive words......Page 139
4. The distance to nonprimitive words......Page 140
5. Concluding remarks......Page 144
References......Page 145
1. Introduction......Page 148
2. Fine convergence and continuous Fine convergence......Page 150
3. Fine computability......Page 154
4. Fine computable functions......Page 157
5. Effective Fine convergence......Page 160
6. Recursive functional equations and Fine computable functions......Page 163
References......Page 171
1. Introduction......Page 172
2. Basic Definitions and Preliminaries......Page 174
3. Context-Free Grammars Extended with Permutation Rules......Page 176
References......Page 186
1. Introduction......Page 188
2.1. Chomsky-hierarchy: basic notions and de nitions......Page 189
2.2. Derivation graphs for phrase-structure grammars......Page 192
2.3. Derivation trees for context-free case......Page 193
2.4. Derivation graphs for context-sensitive languages......Page 195
2.4.1. Atanasiu's approach for monotonous grammars......Page 196
3. A New Concept of Derivation Tree in Context-Sensitive Case......Page 198
4. Left-Most Derivations in Context-Sensitive Case......Page 203
Acknowledgements......Page 207
References......Page 208
1. Introduction......Page 210
2. Restarting Automata......Page 213
3. Finite-State Acceptors and Pushdown Automata......Page 219
4. Two-Pushdown Automata......Page 221
5. Transformations Computed by Deterministic Types of Automata......Page 224
References......Page 229
1. Introduction......Page 232
2. Initial Literal Shu es of Uniform Codes......Page 234
References......Page 246
