In this chapter we studied homomorphic representations of context-free languages by means of Dyck languages. Using graphical approaches we gave an alternative proof of the Chomsky-Sch¨utzenberger theorem. To reach the Chomsky-Sch¨utzenberger theorem we built, in Section3.2, atransition-like diagram for context-free grammars in Dyck normal form (introduced in Subsection 2.3.5, Definition 2.14). By improving this transition diagram, in Section 3.3 we refined the regular language provided by the Chomsky-Sch¨utzenberger theorem. From the refined graphical representation of derivations in a context-free grammar in Dyck normal form, used in Section 3.3, we built a transition diagram for afinite automaton and aregular grammar that generates aregular superset approximation of the original context-free language.
Results concerning the Dyck normal form, homomorphic representations of context-free languages, and regular superset approximations of context-free languages have been merged into a single paper in [35].
A challenging problem for further investigations may be to further refine this superset approximation depending on the type of the grammar (e.g. nonself-embedding or un-ambiguous) or on the size of the grammar (e.g. number of nonterminals, rules, etc.) generating a certain context-free language. In [43] it is proved that optimal (minimal) superset approximations exist for several kind of context-free languages, but no specifi-cation is provided of how the existing minimal approximation can be built starting from the context-free language it approximates. It would be challenging to further investigate whether there exist subsets of context-free languages for which it would be possible to build a minimal superset approximation (by using the graphical method proposed in this chapter).
The method used throughout this chapter is graphically constructive, and it shows thati.
derivational structures in context-free grammars can be better described through nested systems of parenthesis (Dyck languages), andii.the Chomsky-Sch¨utzenberger theorem may render a good and efficient approximation for context-free languages. Furthermore, the method provides a graphical framework to handle derivations and descriptional struc-tures in context-free grammars, which may be useful in further complexity investigations of context-free languages.
Chapter 4
Asymptotic Growth,
Computational Models, and Complexity Classes
It is amazing how little we need to have every-thing! (C. H. Papadimitriou, [163])
Utilizing a sequence of elementary operations, a Turing machine, unlike a computer, has no limitation on the amount of time or memory available for a computation. (T. A. Sudkamp, [199])
4.1 Asymptotic Growth Ratio
To optimize a system, first it is necessary to know which are the limits that bound the system functionality, i.e., the upper and lower bounds. Then improve the system as much as possible such that it performs the same tasks but within better limits. This
“optimization” formula can be applied to any algorithm or abstract machine in order to increase its efficiency. An algorithm may be calledefficient if it uses as less as possible resources without affecting its functionality. The main complexity measures are time and space. Sometimes to find the most efficient algorithm/abstract machine may be an idealistic aim, because decreasing some resources may lead to the increase of some others. Therefore, it is useful to know how the considered measures depend on each other, i.e., to know which are thetrade-offs that characterize the measures.
The main tool used to achieve the above goals is the so called asymptotic analysis, which investigates how the amount of resources spent by an algorithm (or an abstract machine) grows as a function of the size of the input, as the size of the input approaches infinity. If the corresponding function is unintuitive, such as a sum or a product of several elementary functions, in terms of the input size, an asymptotic approximation of the initial function, in terms of the most appropriate function concerning the order of magnitude, is required.
For surveys and applications of asymptotic analysis in computer science, especially in analysis of algorithms and complexity classes, the reader is referred to [44, 86, 125].
There are three types of asymptotic approximations, usually called asymptotic notations, asymptotic upper bounds provided byO(·) and o(·) notations,asymptotic lower bounds provided by Ω(·) and ω(·) notations, and asymptotic equivalence relation provided by Θ(·) notation.
4.1.1 Asymptotic Upper Bounds
An asymptotic upper bound is an approximation of a function in terms of the most appropriate function of the same or greater magnitude. Formally, we have
Definition 4.1. Letf, g:N→R be two functions.
- We say that f(n) is big-O of g(n), denoted by f(n) = O(g(n)), if and only if there exist two positive constants cand n0 such that |f(n)| ≤c|g(n)|, for all n≥n0.
- We say that f(n) issmall-o ofg(n), denoted by f(n) =o(g(n)), if and only if for any positive constant cthere exists a positive constantn0 such that|f(n)| ≤c|g(n)|, for all n≥n0.
Remarks 1. f(n) = O(g(n)) means that f(n) is a member of the set O(g(n)) which is composed of all functions asymptotically upper bounded by g(n). In other words, O(g(n)) is composed of functions of equal, within a constant factor, or smaller magnitude than g(n), as n approaches infinity. In terms of limit operation1, if lim
n→∞ then f(n) = O(g(n)). The O(·) notation allows asymptotic upper approximations of f(n) in terms of a function of the same or greater magnitude, multiplied by a constant factor. Hence, O(1) is the set of at most constant growth functions, O(logn) is the set of at most logarithmic growth functions, O(n) is the set of at most linear growth functions, O(nc), c≥1, is the set of polynomial growth functions, while O(cn), c≥1, is the set of exponentially growing functions, and so on. The next hierarchy hold:
...⊂ O(21n)⊂ O(n1)⊂ O(1)⊂ O(log logn)⊂ O(logn)⊂ O(√
n)⊂ O(n)⊂ O(nlogn)⊂
1Recall that the converse does not hold. A counter example can be provided by the functionsg(n) =n andf(n) =nsinn. Clearly,nsinn∈ O(n), but lim
Chapter 4. Asymptotic Growth, Computational Models, and Complexity Classes
O(nc)⊂ O(cn)⊂ O(n!)⊂ O(nn) ⊂ O(22n) ⊂..., which certainly can be enriched with infinitely many other classes.
2. f(n) = o(g(n)) means that f(n) is a member of the set o(g(n)) which is composed of all functions asymptotically strict upper bounded by g(n), as n approaches infinity, i.e., lim upper approximations off(n) in terms of functions of greater magnitude than f(n).
3. o(g(n))⊂ O(g(n)).
4.1.2 Asymptotic Lower Bounds
An asymptotic lower bound is an approximation of a function in terms of the most appropriate function of the same or lower magnitude. Formally, we have
Definition 4.2. Letf, g:N→R be two functions.
- We say thatf(n) isbig-Ω ofg(n), denoted byf(n) = Ω(g(n)), if and only if there exist two positive constants cand n0 such that|f(n)| ≥c|g(n)|, for all n≥n0.
- We say thatf(n) issmall-ω of g(n), denoted byf(n) =ω(g(n)), if and only if for any positive constant cthere exists a positive constantn0 such that|f(n)| ≥c|g(n)|, for all n≥n0.
Remarks1. f(n) = Ω(g(n)) means that f(n) is a member of the set Ω(g(n)) which is composed of all functions asymptotically lower bounded byg(n). In other words, Ω(g(n)) is composed of functions of equal, within a constant factor, or greater magnitude than g(n), as n approaches infinity. In terms of limit operation, if lim
n→∞ f(n) = Ω(g(n)). The Ω(·) notation allows asymptotic lower approximations of f(n) in terms of a function of the same or lower magnitude, multiplied by a constant factor.
2. f(n) = ω(g(n)) means that f(n) is a member of the set ω(g(n)) which is composed of all functions asymptotically strict lower bounded by g(n), as n approaches infinity, i.e., lim lower approximations off(n) in terms of functions of smaller magnitude than f(n).
3. ω(g(n))⊂Ω(g(n)) andω(g(n))∩ O(g(n)) =∅.
4.1.3 Asymptotic Equivalence
Definition 4.3. Letf, g :N→ Rbe two functions. We say that f(n) isbig-Θ of g(n), denoted byf(n) = Θ(g(n)), if and only if there exist three positive constantsc1,c2, and n0 such that c1|g(n)| ≤ |f(n)| ≤c2|g(n)|, for all n≥n0.
Remarks1. f(n) = Θ(g(n)) means that f(n) grows at the same rate asg(n), and that f(n) is a member of the set Θ(g(n)) which is composed of all functions asymptotically equivalent to g(n), i.e., functions of equal magnitude as g(n), within some constant factors. In terms of limits, if 0 < lim
n→∞
f(n) g(n)
< ∞ then f(n) = Θ(g(n)). The Θ(·) notation allows in the same time asymptotic lower and upper approximations off(n) in terms of the same function of the same magnitude, multiplied by some constant factors.
Hence, the Θ(·) notation provides the most appropriate approximation of a function.
2. Θ(1) is the set of constant growth functions, Θ(log(n)) is the set of logarithmic equivalent growth functions, Θ(n) is the set of linear equivalent growth functions, Θ(nc), c≥1, is the set of polynomially equivalent growth functions, while Θ(cn), c≥1, is the set of exponential equivalent growth functions. Hence, the main difference between Θ(cn) andO(cn),c≥1, is that Θ(cn) cannot contain, for instance, logarithmic functions, which are included in O(cn). Therefore, Θ(g(n))⊂ O(g(n)). The same observation holds for Θ(g(n)) and Ω(g(n)), i.e., Θ(g(n))⊂Ω(g(n)). Hence, O(g(n))∩Ω(g(n)) = Θ(g(n)).