EOL forms

Summary In this paper the notions of L form and its interpretations are introduced to define families of structurally similar L systems. The families of L systems thus defined are studied from a number of different points of view. It is felt that this novel approach will shed new light on many questions concerning L systems.     

On generators and generative capacity of EOL forms

Summary In this paper we study the generative capacity of EOL forms from two different points of view. On the one hand, we consider the generative capacity of special EOL forms which one could call linear like and context free like, establishing the existence of a rich variety of non-regular sub-EOL language families. On the other hand, we propose the notion of a generator L of a language family We mean by this that any synchronized EOL system generating L generates — if understood as an EOL form — all languages of . We characterize the generators of the family of regular languages, and prove that other well known language families do not have generators.Partially supported under NSE Research Council of Canada, grant No. A-7700     

On pure,terminal invariant and nonterminal invariant interpretations of EOL forms

This paper (re) considers some basic axioms of the theory of EOL forms. Two new kinds of interpretations are introduced; they form natural steps in-between ordinary and pure interpretations. Various properties of those interpretations are proved and several open problem concerning pure interpretations are solved. In particular certain results are proved which show that synchronized EOL forms have a natural place in the theory of EOL forms (independently of their role as the normal form for EOL systems on language level).     

废旧产品“垃圾零填埋”

<正>富士施乐爱科制造(苏州)有限公司实现生产再生材料1,500吨,再资源化率高达99.8%近日,全球领先的文件管理专家——富士施乐宣布位于中国苏州的整合资源循环系统——富士施乐爱科制造(苏州)有限公司成功实现"垃圾零填埋"的环保目标,其2010年的废旧设备和硒鼓的循环利用率达到99.8%。     

A combinatorial property of EOL languages

Let be an alphabet and II its nontrivial binary partition. Each word over can uniquely be decomposed in subwords (called blocks) consisting of letters of II _i only,i {1,2}. LetK ^*.K has a long block property (with respect to II), abbreviated asLB-property, if there exists a functionf:N ⁺ N ⁺ such that for everyw K and every positive integerm the number of blocks of length at mostm inw is bounded byf(m). K has a clustered block property (with respect to II), abbreviated asCB-property, if there exists a positive integern _o and a growing functiong:N ⁺ N ⁺ such that for everyw K and for every positive integerm the blocks of length at mostm can be covered by at mostn _o segments of length at mostg(m).It is proved that aCB-property always implies aLB-property but not necessarily other way around. It is proved that an EOL language has aLB-property if and only if it has aCB-property.     

Networks of evolutionary processors: computationally complete normal forms

Networks of evolutionary processors (NEPs, for short) form a bio-inspired language generating computational model that was shown to be equivalent to the model of phrase-structure grammars. In this paper, we analyse different restricted variants of NEPs that preserve the computational power of the general model. We prove that any recursively enumerable language can be generated by a NEP where the derivation rules can be applied at arbitrarily chosen positions, the control of the communication is done by finite automata with at most three states, and either the rule sets are singletons or the underlying graph is a complete graph. If one uses networks with arbitrary underlying graphs and allows the additional application of insertions and deletions only to the right-most or the to left-most position of the derived words for some nodes, then we only need automata with only one state to control the communication in the network. Clearly, this result is optimal; moreover, finite automata with two states are necessary and sufficient in order to generate all the recursively enumerable languages when the derivation rules can be applied only at arbitrarily chosen positions.     

On complete one-way functions

Complete constructions play an important role in theoretical computer science. However, in cryptography complete constructions have so far been either absent or purely theoretical. In 2003, L.A. Levin presented the idea of a combinatorial complete one-way function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post correspondence problem. We also present the properties of a combinatorial problem that allow a complete one-way function to be based on this problem. The paper also gives an alternative proof of Levin’s result.     

On good ETOL forms

This paper continues the study of ETOL forms and good EOL forms done by Maurer, Salomaa and Wood. It is proven that binary very complete ETOL forms exist, good synchronized ETOL forms exist and that no propagating or synchronized ETOL form can be very complete.     

On invariant curve forms

A class of axis-independent curve algorithms is investigated, in two- and three-dimensional space, using simple group-theoretic methods. In two dimensions the analysis provides a general curve form not previously considered in Computer Aided Geometric Design. In the three-dimensional case analogous arguments produce no new general axis-dependent curve forms and this is seen to be a consequence of the more complex structure of the rotation group of three-space.     

EOL languages are not codings of FPOL languages

One of the useful results concerning EOL languages states that a language is an EOL language if and only if it is a cording of OL language. In this paper we retine this result by demonstrating that there exist EOL languages that are not codings of languages that are generated by propagating OL systems with finite axiom sets. This solves Problem 10 from the L Systems Problem Book '75.     

The equality of EOL languages and codings of ol languages

It is proved that a language is a coding (a letter-to-letter homomorphism) of a OL language, if, and only if, it is an EOL language.     

On quasi-interpretations of grammar forms

The notions of a grammar form and its interpretations were introduced to describe families of structurally related grammars. Basically, a grammar formG is a (context-free) grammar serving as a master grammar and the interpretation operator defines a family of grammars, each structurally related toG. In this paper, a new operator yielding a family of grammars, is introduced as a variant of . There are two major results. The first is that and commute. The second is that for each grammar formG, the collection of all families of grammars ,G′ in , is finite. Expressed otherwise, the second result is that for each grammar formG there is only a bounded number of grammar forms in (G) no two of which are strongly equivalent.     

On higher order centered forms

If the real-valued mappingf has a representation of the formf(x)=f(c)+(x-c) ⁿ h(x), xεX, then we introduce an interval expression which approximates the range of values off over the compact intervalX with ordern+1. The well known centered form is the special casen=1 of this result.     

On non context-free grammar forms

A grammar formF defines via a so-calledinterpretation mechanism, a family of languages(F). In this paper we establish that for many grammar formsF, (the family of context-free languages) implies(F)= _RE (the family of recursively enumerable sets). We conjecture that this is also true in general. Because of this, it seems necessary to use restricted interpretations for non context-free grammar forms, a form giving then rise to a family We compare the obvious alternatives for restricting interpretations and focus attention on two promising alternatives, _Q (_F) and _st(F) and their combination _{Q, st}(F). Using st-interpretations, surprising families can be generated and strong normal form results can be obtained. Closure results and decidability results are also given. UnderQ, st-interpretation, it is possible to characterize a number of well-known families of languages between _CF and _RE, including the families of EOL, ETOL, matrix and scattered context languages.Part of this work was carried out while the third and fourth authors were visiting the University of Karlsruhe. Part of this work was supported by the Natural Sciences and Engineering Research Council of Canada Grant No. A-7700.     

On log-tape isomorphisms of complete sets

In this paper we study log n-tape computable reductions between sets and investigate conditions under which log n-tape reductions between sets can be extended to log n-tape computable isomorphisms of these sets. As an application of these results we obtain easy to check necessary and sufficient conditions that sets complete under log n-tape reductions in NL, CSL, P, NP, PTAPE, etc. are log n-tape isomorphic to the previously known complete sets in the respective classes. As a matter of fact, all the “known” complete sets for NL, CSL, P, NP, PTAPE, etc. are now easily seen to be, respectively, log n-tape isomorphic. These results strengthen and extend substantially the previously known results about polynomial time computable reductions and isomorphisms of NP and PTAPE complete sets. Furthermore, we show that any set complete in CSL, PTAPE, etc. must be dense and therefore, for example, cannot be over a single letter alphabet.     

On grammar forms with terminal context

Summary A context-free grammar form G defines a family of context-free grammars {ie397-01}(G). In this paper {ie397-02}(G) is extended to give the family of terminal context grammars {ie397-03}(G), which were introduced by Book [4]. It is shown that the families of languages defined by {ie397-04}(G) and {ie397-05}(G) are equal when G is an -free context-free grammar form. This generalizes the result of Book [4] for context-free grammars and underlines the usefulness of the notion of grammar forms in formal language theory.The work of the second author was carried out partially under a National Research Council of Canada Grant. No. A-7700 and partially under the auspices of the University of Karlsruhe     

On strict interpretations of grammar forms

Strict interpretations of grammar forms are studied with respect to parsing, ambiguity, and decidability for intersection and containment. In particular, a parsing procedure for an arbitrary strict interpretation grammar is given which is based on a given parsing method for the master grammar. Time and space bounds on the new procedure are then obtained. Each ambiguous interpretation grammar of an unambiguous grammar form can be converted to an equivalent unambiguous interpretation of the same grammar form. Unambiguity is always decidable for strict interpretation grammars of unambiguous grammar forms. Also, for languages obtained from compatible strict interpretations of an unambiguous grammar form, the following problems are solvable: empty intersection, finite intersection, containment, and equality.Portions of this paper were presented at (i) the 3rd ACM Symposium on Principles of Programming Languages, Jan. 1976, under the title, The Influence of Productions on Derivations and Parsing, and (ii) the 5th Symposium on Mathematical Foundations of Computer Science, Sept. 1976.This author was supported in part by a Guggenheim Fellowship and by NSF Grant No. 42306 and MCS 73-03380.This author was supported in part by NSF Grant No. MCS76-10076.