Implicit complexity over an arbitrary structure: Quantifier alternations

We provide machine-independent characterizations of some complexity classes, over an arbitrary structure, in the model of computation proposed by L. Blum, M. Shub, and S. Smale. We show that the levels of the polynomial hierarchy correspond to safe recursion with predicative minimization and the levels of the digital polynomial hierarchy to safe recursion with digital predicative minimization. Also, we show that polynomial alternating time corresponds to safe recursion with predicative substitutions and that digital polynomial alternating time corresponds to safe recursion with digital predicative substitutions.     

Query languages for sequence databases: termination and complexity

This paper develops a query language for sequence databases, such as genome databases and text databases. Unlike relational data, queries over sequential data can easily produce infinite answer sets since the universe of sequences is infinite, even for a finite alphabet. The challenge is to develop query languages that are both highly expressive and finite. This paper develops such a language as a subset of a logic for string databases called Sequence Datalog. The main idea is to use safe recursion to control and limit unsafe recursion. The main results are the definition of a finite form of recursion, called domain-bounded recursion, and a characterization of its complexity and expressive power. Although finite, the resulting class of programs is highly expressive since its data complexity is complete for the elementary functions     

Algebraic solutions to recursion schemes

The main problem in recursive scheme theory is determining how to solve a scheme and express its solution. Up to now this was always achieved by adding restrictive hypotheses either on the schemes themselves, or on the domains where they take their values, e.g., assuming the domains have a metric or an order structure and are complete with respect to this structure, or are iterative. Here we develop a strictly algebraic theory of recursion schemes with second-order substitutions. As it is strictly algebraic, the theory applies not only to all recursion schemes on trees, but also to recursion schemes on arbitrary algebras presented in the usual way by generators and relations. In particular, this gives a semantics for nondeterminism and for process algebras.     

Partial and Nested Recursive Function Definitions in Higher-order Logic

Based on inductive definitions, we develop a tool that automates the definition of partial recursive functions in higher-order logic (HOL) and provides appropriate proof rules for reasoning about them. Termination is modeled by an inductive domain predicate which follows the structure of the recursion. Since a partial induction rule is available immediately, partial correctness properties can be proved before termination is established. It turns out that this modularity also facilitates termination arguments for total functions, in particular for nested recursions. Our tool is implemented as a definitional package extending Isabelle/HOL. Various extensions provide convenience to the user: pattern matching, default values, tail recursion, mutual recursion and currying.     

基于 VB 的递归模拟演示程序的实现

为帮助学生对递归调用有深刻的理解,特制作递归模拟演示程序,以使学生对递归调用的内部调用机制有直观的认识,提高课堂的教学效果。演示程序使用VB来实现,具有自动演示和手动单步演示的功能。     

Function algebraic characterizations of the polytime functions

We give function algebraic characterizations of the polynomial time computable functions using unbounded recursion schemes without introducing extra notions such as safe and normal in variables and tiering in word algebras. Received: December 9 1998.     

Blocking in a shared resource environment with batched Poisson arrival processes

We study a variant of the multi-dimensional Erlang blocking model in which customer arrivals require multiple servers and are modelled as batched Poisson processes with arbitrary batch size distribution. We show that the state distribution for the partial batch blocking discipline is a product form, and for the special case of the complete sharing policy, we obtain a one-dimensional recursion for the aggregate state distribution. When the batch size distribution is geometric, our recursion is identical to a recursion due to Delbrouck. This correspondence provides a new interpretation for Delbrouck's recursion, which was introduced to model peaked stream blocking. We show that this correspondence is due to an equivalence between a batched Poisson blocking model with geometrically distributed batches and a blocking model with a linear state dependent arrival process.     

Modeling of conductor losses in capacitors with rectangular and circular plates

Analytic models are developed for the losses in the plates of MIM capacitors. The formulas are derived for the equivalent loss tangent and resistance of the arbitrary thick rectangular electrodes. An equivalent surface resistance is introduced for an arbitrary thick conductor. The accuracy of the model is demonstrated by comparison with rigorous Sonnet simulation and available alternative approach. The formula for the resistance of electrically thick circular electrodes is obtained. The derived expressions are verified via comparison with rigorous HFSS (high frequency structure simulator) simulations using eigenmode solver. © 2008 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2009.     

Bounded monotone recursion and multihead automata

On the basis of bounded monotone recursion, a class BMR of word functions over the alphabet {1, 2} is defined. A new type of a computing device is introduced, which is called a multihead nonerasing automaton with output, or an MH automaton. It is proved that the class BMR coincides with the class MHA of word functions computable by MH automata in polynomial time. Numerous examples of word functions from the class BMR are given.     

Algorithms for corner stitched data-structures

Corner Stitching was first presented by Ousterhout as a data-structure for VLSI CAD. This paper describes the data-structure in detail. It presents, in greater depth than previously, algorithms for the basic operations described in Ousterhout's original paper. The algorithms for enumerating and updating arbitrary rectangular areas are new. Their constant space complexity bounds are an improvement over previous algorithms for those operations that were recursive. From a practical standpoint, the elimination of the recursion has also made them much faster.     

Recursive functions in a data base language for complex objects

The work presented in this paper demonstrates a new method for recursive queries in a complex object data base system. The method is called functional recursion. Most previous approaches express recursive queries by set oriented recursion, i.e. they allow us to define a set M recursively by an equation M = ƒ(M). In contrast to set oriented recursion, functional recursion as defined in this paper allows the user to define a function ƒ recursively by an equation ƒ = F(ƒ). As opposed to recursive functions written in a conventional programming language, the termination criterion which sometimes is rather complex does not have to be programmed by the user but is given implicitly. By providing appropriate parameters to a function, the user can integrate a selection into the recursion in a convenient and natural way. This is not the case for set oriented recursion. When using set recursion, the user is forced to formulate a query which computes more than really needed. It is the task of the optimizer then to push the subsequent selection into the recursion. This means that the user cannot write the query in a natural way and the system then has to figure out what the user wanted. All these problems are avoided when using recursive functions as defined in this paper. Moreover, a solution based on key oriented duplicate elimination is presented which solves the problem of lists and arithmetics in the context of recursive functions. The method is illustrated by bill-of-materials examples and by a railroad example.     

Conversion to tail recursion in term rewriting

Tail recursive functions are a special kind of recursive functions where the last action in their body is the recursive call. Tail recursion is important for a number of reasons (e.g., they are usually more efficient). In this article, we introduce an automatic transformation of first-order functions into tail recursive form. Functions are defined using a (first-order) term rewrite system. We prove the correctness of the transformation for constructor-based reduction over constructor systems (i.e., typical first-order functional programs).     

基于非线性PCA准则的两个盲信号分离算法

该文首先基于Oja定义的非线性PCA准则J1(W),利用矩阵广义逆递推得到一种盲信号分离算法,然后对Karhunen给出的非线性PCA加权误差平方和准则J2(W),采用梯度下降算法和线性寻优而得到另一种自适应盲信号分离算法。对这两个分离算法进行了计算机仿真,仿真结果表明它们的有效性。     

Automatic Visualization of Recursion Trees: a Case Study on Generic Programming

Although the principles behind generic programming are already well understood, this style of programming is not widespread and examples of applications are rarely found in the literature. This paper addresses this shortage by presenting a new method, based on generic programming, to automatically visualize recursion trees of functions written in Haskell. Crucial to our solution is the fact that almost any function definition can be automatically factorized into the composition of a fold after an unfold of some intermediate data structure that models its recursion tree. By combining this technique with an existing tool for graphical debugging, and by extensively using Generic Haskell, we achieve a rather concise and elegant solution to this problem.     

A challenge for atomicity verification

An unpublished algorithm of Haldar and Vidyasankar implements an atomic variable of an arbitrary type T for one writer and one reader by means of 4 unsafe variables of type T, three two-valued safe variables, and one three-valued regular variable. We present this algorithm, and prove its correctness by means of a refinement towards a known specification of an atomic variable. The refinement is a composition of refinement functions and a forward simulation. The correctness proof requires many nontrivial invariants. In its construction, we relied on the proof assistant PVS for the administration of invariants and proofs and the preservation of consistency.     

Algorithms for corner stitched data-structures

Corner Stitching was first presented by Ousterhout as a data-structure for VLSI CAD. This paper describes the data-structure in detail. It presents, in greater depth than previously, algorithms for the basic operations described in Ousterhout's original paper. The algorithms for enumerating and updating arbitrary rectangular areas are new. Their constant space complexity bounds are an improvement over previous algorithms for those operations that were recursive. From a practical standpoint, the elimination of the recursion has also made them much faster.This research was supported by the Australian Government Postgraduate Research Awards Scheme and Xerox Corporation.     

算法复杂性函数渐近优超等价类的结构性质

本文建立了算法复杂性函数渐近优超等价类数学结构,并应用递归论研究中的方法和技巧对该结构的性质进行了系统的研究,证明了该结构具有强Friedberg-Muchnic性质和在偏序意义下的稠密性定理.     

Towards a logic programming methodology based on higher-order predicates

This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules. This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates. We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are

1. Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with afold recursion predicate akin to the fold operators in functional programming.
2. General recursive functions can be re-expressed likewise sincefold allows re-expression of alinrec recursion predicate facilitating linear, unbounded recursion.

     

Topology optimization of nonlinear structures with damping under arbitrary dynamic loading

This study presents an extended unit load method in which the displacement of a chosen degree of freedom (DOF) in a nonlinear structure under arbitrary dynamic loading is expressed as an integration of mutual strain energy density over a continuum domain. This new integral formulation for the displacement of a chosen DOF is developed by using the virtual work principle and can be used for linear or nonlinear structural behaviours. The integral form of the displacement is then used to develop new formulations for structural topology optimization involving arbitrary dynamic loading using the moving iso-surface threshold (MIST) method. Presented are two specific topology optimization problems with two objective functions: (a) to minimize the peak of a chosen displacement; or (b) to minimize the average power spectral density (PSD) of the chosen displacement over a finite time interval. New MIST formulations and algorithms are developed for solving two damping topology optimization problems of a structure under arbitrary dynamic loading, with or without large displacements, and having cellular damping materials with multi-volume fractions. Several numerical examples are presented to demonstrate the validity and efficiency of the presented unit load method and the MIST formulations and algorithms.