|
|
Авторизация |
|
|
Поиск по указателям |
|
|
|
|
|
|
|
|
|
|
Conway J.H. — Regular algebra and finite machines |
|
|
Предметный указатель |
Abstract family of language (AFL) 70
Accessible state 3
Acyclic algebra 104
Algebras, commutative 91
Algebras, conservative 104
Algebras, finite 100—102
Algebras, Gruska's algebra 85
Algebras, Kleene algebras 34
Algebras, radical algebras 88
Algebras, regulator algebras 71
Algebras, S-algebras 27 34 56
Algebras, X-algebras 34 100
Antiderivate 50
Antimachine 50
Applicator [ ] 56 85
Approximations 51—55
Automaton 1
Automaton, non-deterministic 31
Axioms 25 100
Biapplicator [[ ]] 85
Binary machine 3 41
Biproduct : 57
Biregular operations +, :, ** 57 60
Biregular operators 58 61
Biregulators 58
Biregulators in commutative cases 97
Biregulators, decision problems for 138
Biregulators, products of 57 62
Biregulators, table of 58
Bishuffle 59
Bistar 57
Biunit [1, 1] 57
Boiling process 113
Bomb 16
Bomb, combination lock bomb 18
Bomb, discriminant bomb 15
Bomb, transition matrix of 16
Boolean functions 44
Boolean functions in commutative case 96
Boolean functions, computation of 123
Bracket languages (a|b) etc. 126
Breadth b(E) of event 43
Canonical form for context-free language 127
Church's thesis 131
Classes of events and operators 65
Classes of events and operators, the class 82
Classical axioms C1-14 25 34—36
Classical axioms C1-14 for matrices 110
Classical axioms C1-14, insufficiency of 117
Classical equivalence 109
Classical events (C-events) 39
Classical events (C-events), derivatives of 109
Classical events (C-events), matrix star formula for 110
Combination lock 20
Combination lock bomb 18
Commutative algebra 91
Commutative biregulators 97
Commutative biregulators, open convex ditto 99
Commutative equations, minimal solutions 98
Commutative events 91
Companions of a language 85
Complement —E of event 44
Computational techniques 120
Concatenated power 25
Concave operator 72
Conservative algebra 104
Console 3
Constant part o[E] 41
Context-free languages 79
Contraction function 62
Contraction operator 59 61
Convex operator 72
Decision problems, insoluble 137
Decision procedures 33 53 123
Derivate 41
Derivate for classical events 109
Derivate, derivates for languages 86
Derivate, event derivate 43
Derivate, input derivates 41
Derivate, operator derivate 60
Derivate, right, or anti-derivate 50
Derivate, word derivates 41
Detonator 16
Diagram of machine (state diagram) 2
Direct sum 11
Discriminant bomb 15
Distinguishability 3
Distinguishing experiment 11
Divisibility of words 63
Dominating subfactorisation 47
Dual operator 59
Empty event 0 24
Empty word 1 3
Equality testing 123
Event 24
Event, breadth b(E) of event 43
Event, complement —E of event 44
Event, event classes 65
Event, event derivates 43
Event, factors of events 47
Event, length l(E) of event 43
Event, matrices of events 26
Event, regular event 26
Event, representable event 24
Event, reverse event 44 60 66
Event, width w(E) of event 43
Event, X-events 39
Exact (n, m, p)-machine 8
Expansion function 62
Expansion operator 59 61
Experiment 3 7
Experiment, distinguishing experiment 11
Experiment, identifier experiment 12 15 19—20 23
Experiment, length of experiment 8 11
Explorer 20 23
Expression, regular 26 34
Expression, X-expressions 34
Factor matrix 48
Factor theorem for languages 86
Factorial function E! (,...,) 54
Factorisation 47
Factors 47
Factors, calculation with 123
Finite algebras 100—102
Free S-algebras 39 56
Free X-algebras 39
Full AFL 70
Function, regular 26
Function, S-function 65 81
Function, X-function 65
Grammar of language 79
Grammatically linear languages 84
Gruska's algebra 85
Gruska's theorem 84
Halting problem 131
Homomorphism 67
Homomorphism, unit-homomorphism 59 61
Identifier experiment 12 15 19—20 22
Inaccessibility 3
Indistinguishability 3
Inequalities 27
Inequalities , testing for 123
Input (input letter) 1
Input (input letter), input derivate 41
Input (input letter), input vector 26
Insoluble problems 131
Insoluble problems for regular events and biregulators 138
Kleene algebras 34
Kleene's theorem 26
Languages (context-free) 79
| Languages (context-free), bracket languages (a\b) etc. 126
Languages (context-free), canonical form for languages 127
Languages (context-free), class L of languages 82
Languages (context-free), companions of a language 85
Languages (context-free), computation with languages 126
Languages (context-free), derivatives of languages 86
Languages (context-free), factor theorem for languages 86
Languages (context-free), grammatically linear languages 84
Left factor 47
Length l(E) of event 43
Length l(E) of experiment 8 11
Letters, input and output 1
Letters, transient and terminal 79
Linear mechanism 30
Linear operator 56
Machines, (n, m, p)-machine 8
Machines, binary 3 41
Machines, construction from regular expressions 121
Machines, finite 1
Machines, infinite 127
Machines, Mealey machine 2
Machines, minimal machine 5—6
Machines, Moore machine 1
Machines, sequential machine 1
Machines, Turing machine 130
Machines, universal Turing machine 135
Matrix of events 26
Matrix of events, factor matrix 48
Matrix of events, of C-events 110
Matrix star formula Ml 28 40
Maximal solution of semilinear inequalities 127
Mechanism, linear 30
Mechanism, linear, general 45
Moore machine 1
Moore uncertainty principle 21
Moore's theorems 11 12
Non-deterministic automaton 31
Normal system 132
Normaliser 55
Normaliser , computation of 124
o(E) = constant part of E 41
Occurrence 24
Open mapping conjecture 99
Open operator 72
Open operator, convex and commutative 99
Open operator, convex open operators 72
Operations, biregular +, :, ** 57 60
Operations, Boolean 44
Operations, regular, +, ., * 25
Operations, S-operations , ., * 27
Operations, X-operations 34
Operators 56
Operators, biregular 58
Operators, classes of operators 65
Operators, concave operator 72
Operators, contraction operator 59 61
Operators, convex operator 72 83
Operators, derivate = 59
Operators, dual operator 59
Operators, expansion operator 59 61
Operators, inverse operator 124
Operators, open operator 72
Operators, product of operators 68
Operators, star of operator 56 72
Operators, the operators 60 66
Output o() of state 2
Output vector 26
Parikh's theorem 98
Pilling product theorem 68
Polynomial 65
Post Correspondence Problem 133
Problems, undecidable 131
Product of events 25
Product of events, biproduct of operators 57
Product of events, of operator classes 68
Product of events, of operators 68
Product of events, product of biregulators 62
Product of events, product of matrices 26
Production 79 132
Promotion lemma 113
Quotient by indistinguishability 4
Radical algebra 88
Redko theorem on axioms for regular algebra 104
Redko theorem on commutative algebra 93
Reduced form 12
Regular event 26
Regular event, commutative 91
Regular event, conservative 104
Regular expression 26 34
Regular expression, computation from machines 121—122
Regular expression, manipulation of 120
Regular function 26
Regular operations +, ., * 25
Regular operations +, ., * on operators 68
Regulator 57
Regulator, biregulator 58 61
Regulator, regulator algebra 71
Regulator, total regulator 57 63 71
Regulator, X-regulator 66
Representable event 24
Reverse of event 44 60 66
Right derivate 50
Right factor 47
Semilinear inequalities 127
Sequential machine 1
Shuffle 59
Solomaa's axiomatisation 107
Solution of equations 124
Square root 55
Standard algebra (=S-algebra) 27 34 56
Standard algebra (=S-algebra), S-functions 81
Standard algebra (=S-algebra), S-operations 27
Standard algebra (=S-algebra), S-operators 57
Star E* of event 25
Star E* of matrix 28 40
Star E* of operator 56 72
Star E*, bistar 56
Starth root 55
Starth root, computation of 124
State 1
State diagram 2
Subfactorization 47
Sum E + F of events 25
Sum E + F of operators 68
Sum E + F, infinite sum 25 34
Tautology 34
Total regulator 57 63 71
Transient and terminal letters 79
Transition function 2 29
Transition matrix of bomb 16
Transition matrix of machine 26
Truncation by inaccessibility 4
Turing machine 130
Turing machine, universal Turing machine 135
Uncertainty principle 21
Unit event 1 24
Unit event 1, biunit [1, 1] 57
Unit-homomorphism 59 67
Universal Turing machine 135
Vector, input or output 26
Width w(E) of event 43
Word 3
Word, divisibility of words 63
Word, empty word 1 3
Word, word derivate 41
X-algebra 34 40
X-event 39
X-expression 34
X-function 65
X-operations 34
|
|
|
Реклама |
|
|
|