1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 10
Текст из файла (страница 10)
We say that set S satisfies the inclusionproperty associated with A if A ~ S. Any inclusion property is a closure property,by taking the relation R to be the unary relation {(a) : a E A} (notice that wemust take n = 0 in Definition 1.6.3).0Example 1.6.6: We shall occasionally say that a set A ~ D is closed undera function f : Dk H D. There should be no mystery as to what this means,since a function is a special kind of relation. For example, we may say that thenatural numbers are closed under addition.
'Ve mean that for any m, n E N wealso have m + n EN-since (m, n, m + n) is a triple in the "addition relation"over the natural numbers. N is also closed under multiplication, but it is notclosed under subtraction.OExample 1.6.7: Since relations are sets, we can speak of one relation as beingclosed under one or more others. Let D be a set, let Q be the ternary relationon D2 (that is, a subset of (D x D)3) such thatQ = {((a, b), (b, c), (a, c)) : a, b, c ED}.Then a relation R ~ D x D is closed under Q if and only if it is transitive. Weconclude that transitivity is a closure property. On the other hand, reflexivity is aclosure property, because it is the inclusion property of the set {(d,d): d E D}.OA common type of mathematical construction is to pass from a set A tothe minimal set B that contains A and has property P.
By "minimal set B" wemean "a set B that does not properly include any other set B' that also containsA and has property P." Care must be taken, when a definition of this form isused, that the set B is well defined, that is, that there exists only one suchminimal set. Since a set of sets can have many minimal elements or none at all,whether B is well defined depends on the nature of property P. For example, ifP is the property "has either b or c as an element" and A = {a}, then B is notwell defined since both {a, b} and {a, c} are minimal sets with A as a subset andwith property P.However, as the following result guarantees, if P is a closure property, thenthe set B is always well defined:Theorem 1.6.1: Let P be a closure property defined by relations on a set D,and let A be a subset of D.
Then there is a unique minimal set B that containsA and has property P.Proof: Consider the set of all subsets of D that are closed under R 1 , .•• , Rmand that have A as a subset. We call this set of sets S. We need to show that S1.6: Closures and Algorithms39has a unique minimal element B. It is easy to see that S is non empty, since itcontains the "universe" D -itself trivially closed under each R i , and certainlycontaining A.Consider then the set B which is the intersection of all sets in S,B=n S .First, B is well defined, because it is the intersection of a non-empty collectionof sets.
Also, it is easy to see that it contains A -since all sets in S do. Wenext claim that B is closed under all Ri'S. Suppose that aI, ... , an; -I E B, and(al, ... ,an;-I,anJ E R i . Since B is the intersection of all sets in S, it followsthat all sets in S contain aI, ... ,an; -I. But since all sets in S are closed underR i , they all also contain an;. Therefore B must contain an;, and hence B isclosed under R i .
Finally B is minimal, because there can be no proper subsetB' of B that has these properties (B' contains A and is closed under the Ri'S).Because then B' would be a member of S, and thus it would include B .•We call B in Theorem 1.6.1 the closure of A under the relations R 1 , •..
, R",.Example 1.6.8: The set of all your ancestors (where we assume that each personis an ancestor of her- or himself) is the closure of the singleton set containing onlyyourself under the relation {(a, b) : a and b are persons, and b is a parent of a}.<:;Example 1.6.9: The set of natural numbers N is the closure under additionof the set {O, I}. N is closed under addition and multiplication, but not undersubtraction.
The set of integers (positive, negative, and zero) is the closure ofN under subtraction.<:;Example 1.6.10: The reflexive, transitive closure of a binary relation Roversome finite set A defined asR* = {(a, b) : there is a path in R from a to b}(recall Definition 1.6.1) richly deserves its name: It turns out that it is theclosure of R under transitivity and reflexivity -both closure properties.First, R* is reflexive and transitive; for there is a trivial path from a to afor any element a, and if there is a path from a to b, and a path from b to c,then there is a path from a to c. Also, clearly R ~ R*, because there is a pathfrom a to b whenever (a, b) E R.Finally, R* is minimal. For let (a, b) E R*.
Since (a, b) E R*, there is apath (a = al, ... ,ak = b) from a to b. It follows by induction on k that (a, b)must belong to any relation that includes R and is transitive and reflexive.40Chapter 1: SETS, RELATIONS, AND LANGUAGESThe reflexive, transitive closure of a binary relation is only one of severalpossible closures. For example, the transitive closure of a relation R, denotedR+, is the set of all (a, b) such that there is a nontrivial path from a to b in R-it need not be reflexive. And the reflexive, symmetric, transitive closure ofany relation (there is no special symbol) is always an equivalence relation. Aswe shall show next, there are polynomial algorithms for computing all of theseclosures.
0Any closure property over a finite set can be computed in polynomial time!Suppose that we are given relations Rl C;;; Dr" ... , Rk C;;; Drk of various aritiesover the finite set D, and a set A C;;; D; we are asked to compute the closure A* ofA under R 1 , .•. , R k • This can be carried out in polynomial time by a straightforward generalization of the O(n5) algorithm we devised for the transitive closureproblem in the last subsection:Initially A* := Awhile there is an index i, 1 ~ i S k, and ri elements aj,,""and ajr; ED - A* such that (aj,,"" ajr;) E Ri do:add ajr; to A * .ajr;_' EA*It is a straightforward extension of our argument for the transitive closurealgorithm, which we leave as an exercise (Problem 1.6.9), to show that the abovealgorithm is correct, and that it terminates after O(nr+l) steps, where n = JDJand r is the largest integer among rl, ...
, rk. It follows that the closure of anygiven finite set under any closure property defined in terms of given relations offixed arity can be computed in polynomial time. As a matter of fact, in Chapter7 we shall prove a very interesting converse statement: Any polynomial-timealgorithm can be rendered as the computation of the closure of a set under somerelations of fixed arity. In other words, the polynomial algorithm for closureshown above is the mother of all polynomial algorithms.Problems for Section 1.61.6.1. Are the following sets closed under the following operations? If not, whatare the respective closures?(a) The odd integers under multiplication.(b) The positive integers under division.(c) The negative integers under subtraction.(d) The negative integers under multiplication.(e) The odd integers under division.1.6.2.
What is the reflexive transitive closure R* of the relation R = {(a, b),(a, c), (a, d), (d, c), (d, e)}? Draw a directed graph representing R* .411.7: Alphabets and Languages1.6.3. Is the transitive closure of the symmetric closure of a binary relation necessarily reflexive? Prove it or give a counterexample.1.6.4. Let R ~ A x A be any binary relation.(a) Let Q = {(a,b) : a,b E A and there are paths in R from a to bandfrom b to a}.
Show that Q is an equivalence relation on A.(b) Let II be the partition of A corresponding to the equivalence relationQ. Let R be the relation {( S, T) : S, T E II and there is a path inR from some member of S to some member of T}. Show that R is apartial order on II.1.6.5. Give an example of a binary relation that is not reflexive but has a transitiveclosure that is reflexive.1.6.6. Recall the three functions in the beginning of the subsection on rates ofgrowth:f(n) = 1,000,000· n;g(n) = 10· n 3 ;h(n) = 2n.What are appropriate constants c and d for the inclusions f(n) E O(g(n)),f(n) E O(h(n)), and g(n) E O(h(n))? What is the smallest integer n suchthat the values f(n) .::; g(n) .::; h(n)?1.6.7.
Arrange these functions in order of increasing rate of growth. Identify anyfunctions with the same rate of growth:1.6.8. You have five algorithms for a problem, with these running times:n!(a) Your computer executes 10 8 steps per second. What is the largest size nyou can solve by each algorithm in a second?(b) In a day? (Assume that a day is 105 seconds).(c) How would the numbers in (a) and (b) change if you bought a computerten times faster?1.6.9.
Show that the algorithm given in the end of this section correctly computesthe closure of a set A ~ D under the relations Rl ~ Dr" ... , R~, ~ Dr. inO(nr) time, where n = IDI, and r is the maximum of the arities rl, ... ,rk.(Hint: The argument is a straightforward generalization of the one for theO(n 5 ) transitive closure algorithm.)42BChapter 1: SETS, RELATIONS, AND LANGUAGESALPHABETS AND LANGUAGESThe algorithms we studied informally in the last section have much that isleft vague. For example, we have not specified exactly how the relations Rand R* that need to be accessed and modified are represented and stored. Incomputational practice, such data are encoded in the computer's memory asstrings of bits or other symbols appropriate for manipulation by a computer.The mathematical study of the theory of computation must therefore begin byunderstanding the mathematics af strings af symbals.We start with the notion of an alphabet: a finite set of symbols.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
