Parallel generation of infinite images

We introduce a syntactic model for generating sets of finite and infinite images where a finite image can be viewed as an array over finite alphabet and an infinite image is an array with finite number of columns and infinite number of rows. This model, called image grammar, can be considered as a generalization of classical Chromsky grammar.

We study various types of infinite image grammars using Nivat's derivation which is an infinite unrestrictive derivation, Bvichi's (respectively Muller's) which is defined as infinite derivations selected by some repetitive set (respectively sets of rewriting rules). Then we study the combinatorial and language theoretical properties such as complexity measure, closure properties and decidability results. In terms of complexity measure we give a strict infinite hierarchy. We have extended Nivat's and Eilenberg's theorems to infinite images. Unfortunately we prove that Biichi's and McNaughton's theorems cannot be extended to infinite images. We also characterize these families in terms of deterministic image co-substitution and ω-languages     

The Ill-conditioning of infinite element stiffness matrices

In this paper, a method for improving the conditioning of infinite element stiffness matrices is proposed and examined for one-dimensional and two-dimensional infinite elements. This method is a preconditioning technique which is based on a Gram-Schmidt-like transformation induced by general sesquilinear forms. Although the preconditioning method can be applied to many types of infinite elements, it will be applied to improve the conditioning of the popular multipole infinite element. The paper is concluded with numerical examples demonstrating improved conditioning and convergence properties of the preconditioned multipole infinite elements.     

Infinite arrays and infinite computations

A complete metric topology is introduced on the set of all finite and infinite arrays and the topological properties of the space are studied. In this complete metric topology, infinite arrays are the limits of increasing sequences of finite arrays. The notion of successful infinite derivations in Generalized Context-free Kolam Array Grammars, yielding infinite arrays, is a subclass of Generalized context-free kolam array grammars. For this class, the finite array language generated by a reduced grammar in Greibach normal form and the set of infinite arrays generated by it are related through the notion of adherence.     

广义系统的无穷远特征结构

研究了广义系统的无穷远征结构问题,给出了一种计算了广义系统的无穷远特征向量和广义无穷远特征向量的方法,在此基础上,讨了消除广义系统脉冲运动的问题,得到了保证系统无脉冲运动的充要条件。     

Topology on words

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.     

Sparse Regression Ensembles in Infinite and Finite Hypothesis Spaces

We examine methods for constructing regression ensembles based on a linear program (LP). The ensemble regression function consists of linear combinations of base hypotheses generated by some boosting-type base learning algorithm. Unlike the classification case, for regression the set of possible hypotheses producible by the base learning algorithm may be infinite. We explicitly tackle the issue of how to define and solve ensemble regression when the hypothesis space is infinite. Our approach is based on a semi-infinite linear program that has an infinite number of constraints and a finite number of variables. We show that the regression problem is well posed for infinite hypothesis spaces in both the primal and dual spaces. Most importantly, we prove there exists an optimal solution to the infinite hypothesis space problem consisting of a finite number of hypothesis. We propose two algorithms for solving the infinite and finite hypothesis problems. One uses a column generation simplex-type algorithm and the other adopts an exponential barrier approach. Furthermore, we give sufficient conditions for the base learning algorithm and the hypothesis set to be used for infinite regression ensembles. Computational results show that these methods are extremely promising.     

Polynomial-time compression

This paper studies the class ofinfinite sets that have minimal perfect hash functions—one-to-one onto maps between the sets and ^*-computable in polynomial time. We will call such sets P-compressible. We show that all standard NP-complete sets are P-compressible, and give a structural condition,E = ₂ ^E , sufficient to ensure thatall infinite NP sets are P-compressible. On the other hand, we present evidence that some infinite NP sets, and indeed some infinite P sets, are not P-compressible: if an infinite NP setA is P-compressible, thenA has an infinite sparse NP subset, yet we construct a relativized world in which some infinite NP sets lack infinite sparse NP subsets. This world is built upon a result that is of interest in its own right; we determine optimally—with respect to any relativizable proof technique—the complexity of the easiest infinite sparse subsets that infinite P sets are guaranteed to have.     

Ensemble of support vector machines for land cover classification

This letter presents the results of two different ensemble approaches to increase the accuracy of land cover classification using support vector machines. Finite ensemble approaches, based on boosting and bagging and infinite ensemble created by embedding the infinite hypothesis in the kernel of support vector machines, are discussed. Results suggest that the infinite ensemble approach provides a significant increase in the classification accuracy in comparison to the radial basis function kernel‐based support vector machines. While using finite ensemble approaches, bagging works well and provides a comparable performance to the infinite ensemble approach, whereas boosting decreases the performance of support vector machines. Comparison in terms of computational cost suggests that finite ensemble approaches require a large processing time in comparison to the infinite ensemble approach.     

Adherences of languages

This paper studies context-free sets of finite and infinite words. In particular, it gives a natural way of associating to a language a set of infinite words. It then becomes possible to begin a study of families of sets of infinite words rather similar to the classical studies of families of languages.     

Fundamental properties of infinite trees

Infinite trees naturally arise in the formalization and the study of the semantics of programming languages. This paper investigates some of their combinatorial and algebraic properties that are especially relevant to semantics.This paper is concerned in particular with regular and algebraic infinite trees, not with regular or algebraic sets of infinite trees. For this reason most of the properties stated in this work become trivial when restricted either to finite trees or to infinite words.It presents a synthesis of various aspects of infinite trees, investigated by different authors in different contexts and hopes to be a unifying step towards a theory of infinite trees that could take place near the theory of formal languages and the combinatorics of thefree monoid.     

A second order theory of infinite trees

An axiomatic approach based on second order logic for specifying finite data types has been given in [12]. In the present paper we generalize the approach to infinite trees. Data logic CT of infinite trees is introduced and investigated. CT is based on the data logic T of finite trees. For treating infinite objects we heavily rely upon the notions of Bishop'apos;s constructive mathematics. Thus the results of the present paper are closely related with an intuitionistic type theory of infinite trees.     

Projection lemmas for ω-languages

The paper presents projection lemmas relating the infinite behaviour of deterministic and unboundedly branching nondeterministic infinite automata.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

Regular Languages of Thin Trees

An infinite tree is called thin if it contains only countably many infinite branches. Thin trees can be seen as intermediate structures between infinite words and infinite trees. In this work we investigate properties of regular languages of thin trees. Our main tool is an algebra suitable for thin trees. Using this framework we characterize various classes of regular languages: commutative, open in the standard topology, and definable in weak MSO logic among all trees. We also show that in various meanings thin trees are not as rich as all infinite trees. In particular we observe a collapse of the parity index to the level (1, 3) and a collapse of the topological complexity to co-analytic sets. Moreover, a gap property is shown: a regular language of thin trees is either weak MSO-definable among all trees or co-analytic-complete.     

On the numerical evaluation of an oscillating infinite series III

An oscillating infinite series involving product of Bessel function J _o(x) and an oscillating infinite series involving trigonometric function sin(x) were evaluated and computed numerically in [1] and [2] respectively. In this paper, an oscillating infinite series involving product of exponential, Bessel and trigonometric functions is evaluated. The series is transformed first into the sum of two infinite integrals by using contour integration and then the infinite integral with oscillating integrand is transformed through some identities into a finite integral containing modified Bessel function K ₁(x). Finally, theset two integrals are evaluated numerically without any computational difficulties at all.     

无穷零点的渐近线计算

本文从代数函数入手讨论了多变量系统的无穷零点特性,对整数阶和分数阶无穷零点给出了统一的定义,及其渐近线的统一计算公式,并指出了以前有关文献的错误,这对多变量根轨迹渐近特性的研究是有用的。     

Infinite Strings Generated by Insertions

The process of generation of strings over a finite alphabet by inserting characters at an arbitrary place in the string is considered. A topology on the set of strings is introduced, in which closed sets are defined to be sets of strings that are invariant with respect to the insertion of characters. An infinite insertion string is defined to be a set of infinite sequences of insertions ending in the same open sets. The number of infinite insertion strings is proved to be countable. It is proved also that there is a relationship between the countability of the completion of partially well-ordered sets by infinite elements and the fulfillment of an analogue of Dickson's and Higman's lemmas for them.     

Abstract geometrical computation 5: embedding computable analysis

Extended Signal machines are proven capable to compute any computable function in the understanding of recursive/computable analysis (CA), represented here with type-2 Turing machines (T2-TM) and signed binary. This relies on a mixed representation of any real number as an integer (in signed binary) plus an exact value in (−1, 1). This permits to have only finitely many signals present simultaneously. Extracting a (signed) bit, improving the precision by one bit and iterating a T2-TM only involve standard signal machines. For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely many iterations to produce an infinite output. This infinite duration can be provided by an infinite acceleration construction. Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling of accumulations.     

Linear convex stochastic control problems over an infinite horizon

A stochastic control problem over an infinite horizon which involves a linear system and a convex cost functional is analyzed. We prove the convergence of the dynamic programming algorithm associated with the problem, and we show the existence of a stationary Borel measurable optimal control law. The approach used illustrates how results on infinite time reachability [1] can be used for the analysis of dynamic programming algorithms over an infinite horizon subject to state constraints.     

Efficient inclusion testing for simple classes of unambiguous ω-automata

We show that language inclusion for languages of infinite words defined by nondeterministic automata can be tested in polynomial time if the automata are unambiguous and have simple acceptance conditions, namely safety or reachability conditions. An automaton with safety condition accepts an infinite word if there is a run that never visits a forbidden state, and an automaton with reachability condition accepts an infinite word if there is a run that visits an accepting state at least once.