Mathematical Foundation of Informatics: Proceedings of the Conference Hanoi, Vietnam 25 – 28 October 1999

Mathematical Foundation of Informatics, Long Van Do, Masami Ito9789810246563, 981-02-4656-0

This volume presents research results ranging from those in pure mathematical theory (semigroup theory, graph theory, etc.) to those in theoretical and applied computer science, e.g. formal languages, automata, codes, parallel and distributed computing, formal systems, knowledge systems and database theory.

---

Table of contents :
Contents……Page 10
Preface……Page 6
1 Introduction……Page 12
2 Definitions……Page 13
3 The Growth Function of a Petri Net……Page 14
4 The Growth Function and Representative Complexity……Page 17
5 Remark and Open Problem……Page 20
References……Page 21
1 Preliminaries……Page 24
2 On a criterion for Petri net languages……Page 26
3 An infinite hierarchy of Petri net languages……Page 29
References……Page 31
2 Preliminaries……Page 34
3 Testing unique decipherability of finite words……Page 36
3.2 A Test by product of automata……Page 37
4.1 A Test by product of automata……Page 39
4.2 A Test for strict-codes……Page 40
4.3 Another test for Codes and w-Codes……Page 41
Rational case……Page 43
Tests by quotients of languages……Page 45
References……Page 47
1 Introduction……Page 48
2 Preliminaries……Page 49
3 Algorithms description……Page 50
5 Conclusions and future works……Page 51
References……Page 52
1 Formal Concept Analysis and Rough Set Theory……Page 54
2 FCA-based Conceptual Clustering……Page 55
3 Approximate Conceptual Clustering……Page 57
4 Document Clustering based on a Tolerance Rough Set Model……Page 58
References……Page 63
1 Introduction……Page 66
3.1 Bi-Partitioning: MC2P……Page 67
3.2 Min-Cut Balanced Bi-Partioning: MCB2P……Page 68
3.3 Hypergraph……Page 69
3.4 Geometric Representation……Page 70
3.5 Replication……Page 71
4 Our heuristic……Page 72
4.1 Example……Page 73
References……Page 75
2 Results and Conjecture……Page 78
References……Page 81
1 Introduction……Page 82
2 Deterministic Directable Automata……Page 83
3 Nondeterministic Directable Automata……Page 85
4 Commutative Nondeterministic Directable Automata……Page 92
References……Page 93
1 Introduction……Page 96
2 Notions and Notation……Page 98
3 Maximal Solid Codes in a+b+ U a+b+a+b+……Page 99
4 Properties of Near-Inverses……Page 101
5 Redundancy of Maximal Solid Codes in a+b+ U a+b+a+b+……Page 103
6 Concluding Remarks……Page 104
References……Page 105
1 Introduction……Page 106
2 Maximal independent sets in length-compatible order……Page 108
3 Factor order. Infix codes……Page 115
4 Subword order. Hypercodes……Page 117
References……Page 120
1 Introduction……Page 122
2 Preliminaries……Page 123
3 Strong congruence recognition……Page 125
4.1 Nice semigroups……Page 127
4.2 Semigroups with commutative stabilizers……Page 128
References……Page 129
1. Introduction……Page 130
2. Some concepts and results……Page 131
Algorithm DERIVES……Page 137
Algorithm NONREDUN……Page 138
References……Page 140
2. Measures for attribute selection……Page 142
3. The measure RN……Page 143
4. Some characteristics of the measure RN……Page 144
5. Conclusion……Page 150
References……Page 151
1 Introduction……Page 152
2 Problems Defined by B-Circuits……Page 153
3 Closed Classes of Boolean Functions……Page 154
4 Circuit Value……Page 158
5 Satisfiability and Tautology……Page 159
6 Quantifiers……Page 161
7 Counting Functions……Page 163
8 The Threshold Problem……Page 165
References……Page 166
The Rational Skimming Theorem Jacques Sakarovitch……Page 168
1 The Schutzenberger covering……Page 169
2 K-automata……Page 171
3 K-coverings……Page 173
4 The skimming theorem……Page 178
References……Page 182
1. Introduction and Notation……Page 184
2. Preliminary Lemmas……Page 185
3. Main Results……Page 188
Reference……Page 192
1 Introduction……Page 194
2 Notations and definitions……Page 195
3 General reduction results……Page 197
4 Main result……Page 199
References……Page 203
1. Introduction……Page 206
2. The main result……Page 208
References……Page 213