This volume is devoted to the main areas of mathematical logic and applications to computer science. There are articles on weakly o-minimal theories, algorithmic complexity of relations, models within the computable model theory, hierarchies of randomness tests, computable numberings, and complexity problems of minimal unsatisfiable formulas. The problems of characterization of the deduction-detachment theorem, 1-induction, completeness of Lesniewski's systems, and reduction calculus for the satisfiability problem are also discussed. The coverage includes the answer to Kanovei's question about the upper bound for the complexity of equivalence relations by convergence at infinity for continuous functions. The volume also gives some applications to computer science such as solving the problems of inductive interference of languages from the full collection of positive examples and some negative data, the effects of random negative data, methods of formal specification and verification on the basis of model theory and multiple-valued logics, interval fuzzy algebraic systems, the problems of information exchange among agents on the base topological structures, and the predictions provided by inductive theories.
Author(s): R. Downey, S S Goncharov, H Ono
Publisher: World Scientific
Year: 2006
Language: English
Pages: 329
City: Singapore; Hackensack, NJ
CONTENTS......Page 8
Preface......Page 6
1. Introduction......Page 10
2. Definitions and Preliminaries......Page 11
3. Closure Relations......Page 15
4. The Deduction-Detachment Theorem......Page 18
5. DDT and Protoalgebraic Hilbert Systems......Page 22
References......Page 24
1. Background and preliminaries......Page 26
2. One-element Rogers semilattices......Page 28
References......Page 39
1. Properties of 2-formulas......Page 40
2. Main theorem......Page 46
References......Page 49
1. Introduction and Motivation......Page 50
2. Preliminaries......Page 51
3. Model Checking Game for SOEPDL......Page 54
4. Reduction to CTL......Page 56
References......Page 58
1. Introduction......Page 60
References......Page 66
1. Introduction......Page 67
2. Marker's construction......Page 69
3. On one-to-one representation of E02-sets......Page 71
4. N1-categorical theory with computable models......Page 72
5. N0-categorical theory with computable model......Page 74
6. Complexity of index sets......Page 76
References......Page 78
1. Preamble......Page 79
2. l1......Page 80
3. lP (p > 1)......Page 82
4. The O notation......Page 84
5. O and loo......Page 86
6. More about loo......Page 89
7. c0 and Kanovei's question
......Page 91
References......Page 97
1. Introduction......Page 99
2. Preliminaries......Page 104
3. Identification with Finite Negative Information......Page 107
4. Some other Negative Information Models......Page 108
5. Identification with Open Negative Information......Page 109
6. Learning with Negative Counterexamples......Page 112
7. Learning With Subset Queries......Page 117
8. Random Negative Examples......Page 119
References......Page 120
Introduction......Page 122
1. Structure of the nonstandard universe......Page 124
2. Classes Ass2 and L[I]: effective sets......Page 126
3. Effective cardinalities of internal sets......Page 128
4. Effective cardinalities of sets of standard size......Page 129
5. Exteriors and interiors......Page 130
6. Effective cardinalities of Ess1 sets......Page 132
7. Effective cardinalities of IIss1 sets......Page 134
8. Effective sets in the form of quotients......Page 138
9. Equivalence relations with standard size classes......Page 139
10. Monadic partitions......Page 141
11. The proof of the reducibility theorem......Page 143
12. On small and large effective sets......Page 147
13. Nonstandard version of the finite Ramsey theorem......Page 151
References......Page 152
1. Introduction......Page 154
2. Specifications of computer arithmetics......Page 155
3. Arithmetics design method......Page 156
4. Digital number systems......Page 160
5. Application: dataflow computations verification......Page 162
6. Conclusion......Page 163
References......Page 164
2. Lesniewski's Systems......Page 165
3. The Functional Completeness of Y-Protothetic
......Page 169
4. The Functional Completeness of Y-Ontology......Page 170
References......Page 174
1. Introduction......Page 175
2. Notation and Problem Statement......Page 176
3. Reduction Calculus......Page 177
4. A Reduction Algorithm for Tautology Test......Page 180
5. Conclusion......Page 182
References......Page 183
1. Introduction......Page 184
2. Non-vanishing I-algebras......Page 185
3. Ordered semigroup......Page 186
4. Local I-algebras......Page 187
5. Finitely axiomatizable I-algebras......Page 195
7. Nonaxiomatizability of local finitely axiomatizable and w-categorical I-algebras......Page 197
References......Page 198
1. Introduction......Page 200
2. Fuzzification of Boolean-valued models......Page 203
3. Generalized fuzzy models......Page 205
4. Boolean-valued models with atomic Boolean algebras......Page 208
References......Page 211
1. Introduction......Page 212
2. Permanents and determinants of Boolean matrices......Page 213
3. Permanent expansion of Boolean matrices and its uniqueness......Page 215
4. The group of invertible Boolean matrices and permanent expansion......Page 217
5. Examples of nonnegative Boolean binary relations......Page 219
6. Interiorities and their properties......Page 220
References......Page 222
1. Introduction......Page 224
2. Effective Randomness Tests for Outer Measures......Page 226
3. Nullsets and Kolmogorov complexity......Page 232
4. A Hierarchy of Randomness Tests......Page 235
References......Page 240
1. Introduction......Page 242
2. General Definitions, Notation, Preliminary Facts......Page 246
3. Admissibility of Logical Consecutions, Preliminary Discussion......Page 248
4. Decidability of Lt,y(Z) w.r.t. Admissible Consecutions
......Page 251
References......Page 260
Isomorphisms and Definable Relations on Rings and Lattices......Page 263
1. The lattice......Page 264
2. The ring......Page 267
3. The basic results......Page 270
References......Page 271
1. Induction......Page 272
2. Laws......Page 276
3. The Probability of Events and Sentences......Page 277
4. The Probabilistic Laws on m......Page 278
6. Probabilistic Maximum Specific Laws......Page 280
7. The Solution of the Statistical Ambiguity Problem......Page 282
References......Page 284
1. Introduction......Page 286
2. The category Rep......Page 288
3. (Co)completeness of Rep......Page 292
References......Page 295
1. Introduction......Page 297
2. Conceptual Semantic Systems......Page 301
3. Temporal Conceptual Semantic Systems......Page 303
4. An Example of a Temporal Conceptual Semantic System......Page 305
5. Conclusion and Future Research......Page 307
References......Page 308
1. Introduction......Page 311
2. MU-Formulas with Fixed Deficiency......Page 313
3. Minimal Formulas with Simple Structures......Page 314
4. Maximal MU Formulas......Page 315
5. Marginal MU Formulas......Page 317
6. Unique MU Formulas......Page 318
7. MU Formulas with Disjunctive Splitting......Page 321
8. MU Formulas Closed under Splitting......Page 322
10. Homomorphisms Between MU Formulas......Page 324
11. Generalizations......Page 325
References......Page 327
