Top-down tree transducers with regular look-ahead

Top-down tree transducers with regular look-ahead are introduced. It is shown how these can be decomposed and composed, and how this leads to closure properties of surface sets and tree transformation languages. Particular attention is paid to deterministic tree transducers.The research reported here was carried out during a one-year visit of the author to the Dept. of Computer Science of Aarhus University, Aarhus, Denmark.     

Variants of top-down tree transducers with look-ahead

In this article we consider deterministic and strongly deterministic top-down tree transducers with regular look-ahead, with regular check, with deterministic top-down look-ahead, and with deterministic top-down check. We compare the transformational power of these tree transducer classes by giving a correct inclusion diagram of the tree transformation classes induced by them. Along with the comparison we decompose some of the examined classes into simpler classes and we introduce the concept of the deterministic top-down tree automata with deterministic top-down look-ahead. We show that these recognizers recognize a tree language class which is strictly between the class of regular tree languages and the class of tree languages recognizable by deterministic top-down tree automata. We also study the closure properties of the examined tree transformation classes. We show that some classes are closed under composition while others, for example the class of tree transformations induced by deterministic top-down tree transducers with deterministic top-down look-ahead, are not.     

Restricted ground tree transducers

We consider restricted versions of ground tree transducers: total, deterministic, and symmetric subclasses and all other subclasses created by applying any combination of these restrictions. We present the inclusion diagram of the tree transformation classes induced by these restricted ground tree transducers. We show that the following four classes of term relations are the same: (i) tree transformations induced by symmetric deterministic ground tree transducers, (ii) congruence relations on term algebras induced by reduced ground term rewriting systems, (iii) congruence relations on term algebras induced by convergent ground term rewriting systems, and (iv) finitely generated congruence relations on term algebras. As a by-product of our results, we obtain a new ground completion algorithm. Moreover, we show that the following three classes of term relations on term algebras with at least one non-nullary function symbol are also the same: (i) tree transformations induced by total symmetric deterministic ground tree transducers, (ii) congruence relations on term algebras of finite index, (iii) finitely generated congruence relations on term algebras of which the trunk is the whole set of terms.     

Superlinear deterministic top-down tree transducers

Denote byDT, l-DT, andnd-HOM the class of tree transformations induced by deterministic top-down tree transducers, linear deterministic top-down tree transducers, and nondeleting homomorphism tree transducers, respectively. In this paper the classsl-DT of tree transformations induced by superlinear deterministic top-down tree transducers is considered. Some basic properties ofsl-DT are shown. Among others, it is proved thatsl-DT is not closed under composition; thatl-DT—sl-DT ⁺ ≠ Ø withsl-DT ⁺ being the closure ofsl-DT under composition; and thatDT = nd-HOM o sl-DT, where o denotes the operation composition of two classes. Then the hierarchy {sl-DT ⁿ n> 1} is shown to be proper, meaning thatsl-DT ⁿ ?sl-DT ⁿ⁺¹, forn≥ 1. Moreover, the same is proved for the hierarchy {t-sl-DT ⁿ n ≥ 1}, wheret-sl-DT is the subclass ofsl-DT induced by total deterministic superlinear top-down tree transducers.     

Linking theorems for tree transducers

Linear extended multi bottom-up tree transducers are presented in the framework of synchronous grammars, in which the input and the output tree develop in parallel by rewriting linked nonterminals (or states). These links are typically transient and disappear once the linked nonterminals are rewritten. They are promoted to primary objects here, preserved in the semantics, and carefully studied. It is demonstrated that the links computed during the derivation of an input and output tree pair are hierarchically organized and that the distance between (input and output) link targets is bounded. Based on these properties, two linking theorems are developed that postulate the existence of certain natural links in each derivation for a given input and output tree pair. These linking theorems allow easy, high-level proofs that certain tree translations cannot be implemented by (compositions of) linear extended multi bottom-up tree transducers.     

A comparison of two variations of a pebble game on graphs

The number of pebbles used in the black [black-white] pebble game corresponds to the storage requirement of the deterministic [non-deterministic] evaluation of a straight line program. Suppose a distinguished vertex of a directed acyclic graph can be pebbled with k pebbles in the black-white pebble game. Then it can be pebbled with k′≤1/2k(k?1)+1 pebbles in the black pebble game.     

Equivalence of finite-valued tree transducers is decidable

A bottom-up finite state tree transducer (FST) M is calledk-valued iff for every input tree there are at mostk different output trees.M is called finite-valued iff it isk-valued for somek. We show that it is decidable for everyk whether or not a given FST M isk-valued. We give an effective characterization of all finite-valued FSTs and derive a (sharp) upper bound for the valuedness provided it is finite. We decompose a finite-valued FSTM into a finite number of single-valued FSTs. This enables us to prove: it is decidable whether or not the translation of an FSTM is included in the translation of a finite-valued FSTM'. We also consider these questions for size-valuedness.     

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.     

基于APDL宏和VB封装的水声换能器有限元分析

为了有效地避免水声换能器有限元优化设计过程中的重复操作,以及降低对设计者专业技术门槛的限制,对AN-SYS的二次开发技术进行了研究。通过APDL(ANSYS parametric design language)宏和VB封装技术的结合使用,在后台调用ANSYS批处理模式执行相应的宏文件,实现了水声换能器的交互式参数化设计。以I类凹筒型弯张换能器为例开发的软件应用情况表明,换能器交互式参数化设计有效可行,并且操作简单,显示直观,具有十分重要的工程应用价值。     

The time complexity of typechecking tree-walking tree transducers

Tree-walking tree transducers can be typechecked in double exponential time. More generally, compositions of k tree-walking tree transducers can be typechecked in (k + 1)-fold exponential time. Consequently k-pebble tree transducers, which form a model of XML transformations and XML queries, can be typechecked in (k + 2)-fold exponential time. The results hold for both ranked and unranked trees.     

Forward and backward application of symbolic tree transducers

We consider symbolic tree automata (sta) and symbolic regular tree grammars and their corresponding classes of tree languages: s-recognizable tree languages and s-regular tree languages. We prove that the following three classes are equal: the class of s-recognizable tree languages, the class of s-regular tree languages, and the class of images of classical recognizable tree languages under tree relabelings. Moreover, the sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. Also, we consider symbolic tree transducers (stt) and prove the following theorems. The syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second one is nondeleting. Backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. There is a linear stt of which the range is not an s-recognizable tree language. Forward application of simple and linear stt preserves s-recognizability. A restricted version of both the type checking problem of simple and linear stt, and the inverse type checking problem of arbitrary stt is decidable. Since we deal with trees over infinite alphabets, we require appropriate conditions on sta and stt such that all the proofs are constructive.     

A comparison of minimax tree search algorithms

Although theoretic performance measures of most game-searching algorithms exist, for various reasons their practicality is limited. This paper examines and extends the existing search methods, and reports on empirical performance studies on trees with useful size and ordering properties. Emphasis is placed on trees that are strongly ordered, i.e., similar to those produced by many current game-playing programs.     

Conversion and parsing of tree transducers for syntactic pattern analysis

The conversion algorithms for two classes of tree transducers, i.e., simple generalized syntax-directed tree translation (SGSDTT) and generalized finite state transformation (GFST), are proposed. A top-down backtrack parsing algorithm for a GFST is presented. The minimum distance structure-preserved error-correcting tree automaton is also extended to be a parser for SGSDTT. Finally, the tree transducers are applied to modeling and analysis of human motion.This work was supported by the NSF Grant IST 79-18884.     

A comparison of decision tree ensemble creation techniques

We experimentally evaluate bagging and seven other randomization-based approaches to creating an ensemble of decision tree classifiers. Statistical tests were performed on experimental results from 57 publicly available data sets. When cross-validation comparisons were tested for statistical significance, the best method was statistically more accurate than bagging on only eight of the 57 data sets. Alternatively, examining the average ranks of the algorithms across the group of data sets, we find that boosting, random forests, and randomized trees are statistically significantly better than bagging. Because our results suggest that using an appropriate ensemble size is important, we introduce an algorithm that decides when a sufficient number of classifiers has been created for an ensemble. Our algorithm uses the out-of-bag error estimate, and is shown to result in an accurate ensemble for those methods that incorporate bagging into the construction of the ensemble     

The equivalence problem for deterministic MSO tree transducers is decidable

It is decidable for deterministic MSO definable graph-to-string or graph-to-tree transducers whether they are equivalent on a context-free set of graphs.