Extended multi bottom–up tree transducers

Extended multi bottom–up tree transducers are defined and investigated. They are an extension of multi bottom–up tree transducers by arbitrary, not just shallow, left-hand sides of rules; this includes rules that do not consume input. It is shown that such transducers, even linear ones, can compute all transformations that are computed by linear extended top–down tree transducers, which are a theoretical model for syntax-based machine translation. Moreover, the classical composition results for bottom–up tree transducers are generalized to extended multi bottom–up tree transducers. Finally, characterizations in terms of extended top–down tree transducers and tree bimorphisms are presented.     

The Complexity of the Exponential Output Size Problem for Top-Down and Bottom-Up Tree Transducers,

The exponential output size problem is to determine whether the size of output trees of a tree transducer grows exponentially in the size of input trees. In this paper the complexity of this problem is studied. It is shown to be NL-complete for total top-down tree transducers, DEXPTIME-complete for general top-down tree transducers, and P-complete for bottom-up tree transducers.     

The Generating Power of Total Deterministic Tree Transducers

Attributed tree transducers are abstract models used to study properties of attribute grammars. One abstraction which occurs when modeling attribute grammars by attributed tree transducers is that arbitrary trees over a ranked alphabet are taken as input, instead of derivation trees of a context-free grammar. In this paper we show that with respect to the generating power this isnotan abstraction; i.e., we show that attributed tree transducers and attribute grammars generate the same class of term (or tree) languages. To prove this, a number of results concerning the generating power of top-down tree transducers are established, which are interesting in their own. We also show that the classes of output languages of attributed tree transducers form a hierarchy with respect to the number of attributes. The latter result is achieved by proving a hierarchy of classes of tree languages generated by context-free hypergraph grammars with respect to their rank.     

多输入多输出系统的数据分层建模

为了高效准确地实现多输入多输出系统的数据建模,本文提出了数据分层建模算法.将多输入多输出数据建模问题分解为一系列单输入多输出的建模问题,同时改进标准遗传编程算法,将单树表示的的个体结构扩展为向量树的进化个体,实现多输出系统的自动建模.通过大量的计算实例表明,这种算法可以实现复杂的多输入多输出系统的建模,提高数据建模的效率和精度.     

Compositions of tree series transformations

Tree series transformations computed by bottom-up and top-down tree series transducers are called bottom-up and top-down tree series transformations, respectively. (Functional) compositions of such transformations are investigated. It turns out that the class of bottom-up tree series transformations over a commutative and complete semiring is closed under left-composition with linear bottom-up tree series transformations and right-composition with boolean deterministic bottom-up tree series transformations.     

One-pass transformations of attributed program trees

Summary The classical attribute grammar framework can be extended by allowing the specification of tree transformation rules. A tree transformation rule consists of an input template, an output template, enabling conditions which are predicates on attribute instances of the input template, and re-evaluation rules which define the values of attribute instances of the output template. A tree transformation may invalidate attribute instances which are needed for additional transformations.In this paper we investigate whether consecutive tree transformations and attribute re-evaluations are safely possible during a single pass over the derivation tree. This check is made at compiler generation time rather than at compilation time.A graph theoretic characterization of attribute dependencies is given, showing in which cases the recomputation of attribute instances can be done in parallel with tree transformations.Part of this work was done while the author was visiting Tartan Laboratories Inc., Pittsburgh, PA, USA     

A Characterization of the Sets of Hypertrees Generated by Hyperedge-Replacement Graph Grammars

A characterization of the languages of hypertrees generated by hyperedge-replacement graph grammars is established. The characterization says that these languages are exactly those described by sets of derivation trees which are output languages of finite-copying top-down tree transducers. Furthermore, the statement remains valid if the tree transducers are required to generate derivation trees in which the right-hand sides of productions are hypertrees and the nonterminal hyperedges are at most as large as the hyperedges in the generated hypertrees. This result is closely related to a similar characterization that was obtained for the case of string graphs by Engelfriet and Heyker some years ago. In fact, the results of this paper also yield a new proof for the characterization by Engelfriet and Heyker. Received August 1997, and in final form May 1998.     

Transformation of Nonlinear MIMO Discrete‐Time Systems into the Extended Observer Form

The paper addresses the problem of transforming discrete‐time multi‐input multi‐output nonlinear state equations into the extended observer form, which, besides the inputs and outputs, also depends on a finite number of their past values. Necessary and sufficient conditions for the existence of the extended coordinate transformation are formulated in terms of differential one‐forms, associated with the input‐output equations, corresponding to the state equations. The difference between the single‐input single‐output and multi‐input multi‐output cases is described. The applicability of the conditions is illustrated by an example.     

Synthesized and inherited functions

In this paper we introduce a new formal model for the concept of syntaxdirected semantics, calledmacro attributed tree transducer (for short: mat tree transducer). This model is based on (noncircular) attributed tree transducers and on macro tree transducers. In the first type of transducer, semantic values are computed by means of meaning names called synthesized attributes, and by means of context names called inherited attributes. Both, synthesized and inherited attributes represent basic semantic values. In the second type of transducer, semantic values are computed by meaning names only which are called states. However, in order to have a means of handling context information, states represent functions over semantic values. The new model integrates attributed tree transducers and macro tree transducers by allowing both, meaning names and context names to represent functions over semantic values. In analogy to the terminology of attributed tree transducers, we call such meaning names and context names also synthesized functions and inherited functions, respectively.We present an inductive characterization of the tree transformation computed by an mat tree transducer. We prove that mat tree transducers are more powerful than both, attributed tree transducers and macro tree transducers. We characterize mat tree transducers by the two-fold composition of attributed tree transducers. This characterization has three consequences: (1) the height of output trees of mat tree transducers is bounded exponentially in the size of the input tree, (2) the composition hierarchy of mat tree transducers is strict, and (3) mat tree transducers are closed under right-composition with top-down tree transducers, but not under left-composition. Moreover, we prove that the addition of inherited attributes does not increase the computational power of macro tree transducers.     

A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions

 In this paper, we consider derivation trees in apex NLC graph languages. We show that for every graph H in arbitrary apex NLC graph language, a decomposition tree of H can be constructed from a derivation tree of H. We also show that there exists a hierarchy in the class of apex NLC graph languages when we restrict the number of nonterminals in the right-hand sides of productions in apex NLC graph grammars. Received: 5 July 1994/12 February 1996     

Equational tree transformations

We define an equational relation as the union of some components of the least solution of a system of equations of tree transformations in a pair of algebras. We focus on equational tree transformations which are equational relations obtained by considering the least solutions of such systems in pairs of term algebras. We characterize equational tree transformations in terms of tree transformations defined by different bimorphisms. To demonstrate the robustness of equational tree transformations, we give equational definitions of some well-known tree transformation classes for which bimorphism characterizations also exist. These are the class of alphabetic tree transformations, the class of linear and nondeleting extended top-down tree transformations, and the class of bottom-up tree transformations and its linear and linear and nondeleting subclasses. Finally, we prove that a relation is equational if and only if it is the morphic image of an equational tree transformation.     

The copying power of one-state tree transducers

One-state deterministic top-down tree transducers (or, tree homomorphisms) cannot handle “prime copying,” i.e., their class of output (string) languages is not closed under the operation L → {$(w$)^f(n) ∥ w?L, f(n) ? 1}, where f is any integer function whose range contains numbers with arbitrarily large prime factors (such as a polynomial). The exact amount of nonclosure under these copying operations is established for several classes of input (tree) languages. These results are relevant to the extended definable (or, restricted parallel level) languages, to the syntax-directed translation of context-free languages, and to the tree transducer hierarchy.     

Equivalence and reduction of expansive tree grammars

The equivalence of nonterminals of an expansive tree grammar is considered. Algorithms are presented for constructing sets of equivalent nonterminals for an expansive tree grammar, for reducing the grammar, and for determining whether two grammars generate the same language.     

High-gain feedback in non-linear control systems†

High-gain state and output feedback are investigated for non-linear control systems with a single additive input by using singular perturbation techniques.

Classical approximation results (Tihonov-like theorems) in singular perturbation theory are extended to non-linear control systems by defining a composite additive control strategy, a control-dependent fast equilibrium manifold and non-linear change of coordinates.

Those tools and an appropriate change of coordinates show that high-gain state feedback and variable structure control systems can be equivalently used for approximate non-linearity compensation in feedback-linearizable systems.

Next the effect of high-gain output feedback is shown to be related to the strong invertibility property and the relative order of invertibility. For strongly invertible systems the slow reduced subsystem coincides with the dynamics of the inverse system when zero input is applied and with the unobservable dynamics when a certain input-output feedback-linearizable transformation is applied.     

Deciding equivalence of top–down XML transformations in polynomial time

Many useful XML transformations can be expressed by deterministic top–down tree transducers. A normal form is presented for such transducers (extended with the facility to inspect their input trees). A transducer in normal form has a unique canonical form which can be obtained by a minimization procedure, in polynomial time. Thus, equivalence of transducers in normal form can be decided in polynomial time. If the transducer is total, the normal form can be obtained in polynomial time as well.     

Nonlinear Control VIA Generalized Feedback Linearization Using Neural Networks

A novel approach to nonlinear control, called Generalized Feedback Linearization (GFL), is presented. This new strategy overcomes one important drawback of the well known Feedback Linearization strategy, in the sense that it is able to handle a broader class of nonlinear systems, namely those having unstable zero dynamics. It is shown that the use of a nonlinear predictor for the system output is a key feature in the derivation of the control strategy. For certain types of systems this predictor can be found as a nonlinear function of the system input and output, allowing an output feedback control solution. The use of Artificial Neural Networks (ANN) to directly parameterize the predictor of the controlled variable when an explicit model for the system is not available, is investigated via computer simulations. This approach is based on the functional approximation capability of multi layer ANN.     

Scattered context grammars that erase nonterminals in a generalized k-limited way

A scattered context grammar erases nonterminals in a generalized k-limited way in a successful derivation, where k is a positive integer, if in every sentential form of a derivation, each of its substrings consisting of nonterminals from which the grammar derives empty strings is of length k or less. This paper demonstrates that if a scattered context grammar generates its sentences in this way, it can be converted to a scattered context grammar without erasing productions; in general, however, this is not possible.     

Nonterminal complexity of tree controlled grammars

This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals.     

Block pulse function approach for the identification of Hammerstein model non-linear systems

Two recursive algorithms based on block pulse functions are presented for identifying continuous Hammerstein models of non-linear systems with (i) a state space model and (ii) an input–output model. Since the continuous non-linear systems are transformed approximately into the corresponding difference equations via block pulse functions, these recursive estimation algorithms can easily be obtained using a derivation similar to that of the discrete-time models expressed by difference equations. Both algorithms derived here are simple and straightforward, and can easily be implemented on-line. As discussed in this paper, these algorithms can also be extended to the identification of certain continuous non-linear systems with a feedback loop or with time delays. The illustrative examples show that these recursive algorithms give satisfactory results for the identification problems of certain continuous non-linear systems.     

Bottom-up and top-down tree transformations— a comparison

The top-down and bottom-up tree transducer are incomparable with respect to their transformation power. The difference between them is mainly caused by the different order in which they use the facilities of copying and nondeterminism. One can however define certain simple tree transformations, independent of the top-down/bottom-up distinction, such that each tree transformation, top-down or bottom-up, can be decomposed into a number of these simple transformations. This decomposition result is used to give simple proofs of composition results concerning bottom-up tree transformations.A new tree transformation model is introduced which generalizes both the top-down and the bottom-up tree transducer.