A prime decomposition theorem for grammatical families

Two basic operations on families of languages, in general, and grammatical families, in particular, are sum (formed by taking unions of member languages) and product (formed by taking unions of pairwise products of member languages). In this paper, a grammatical family is defined to be prime if it is contained in one of two grammatical families whenever it is contained in their product, and the following Prime Decomposition Theorem is then established: Every grammatical family can be represented as a minimal sum of products of primes in a unique way.This theorem leads to a general method for decomposing a grammatical family into simpler ones. A subsequent paper uses this method to obtain a decision procedure for determining whether two grammar forms generate the same grammatical family, as well as a canonical representation for grammatical families.     

A decomposition theorem for finite persistent transition systems

In this paper, we consider finite labelled transition systems. We show that if such transition systems are deterministic, persistent, and weakly periodic, then they can be decomposed in the following sense. There exists a finite set of label-disjoint cycles such that any other cycle is Parikh-equivalent to a multiset of cycles from this set.     

Matrosov theorem for parameterized families of discrete-time systems

A version of Matrosov's theorem for parameterized discrete-time time-varying systems is presented. The theorem is a discrete-time version of the continuous-time result in Loria et al., 2002 (δ-persistency of excitation: a necessary and sufficient condition for uniform attractivity, 2002, submitted for publication). Our result facilitates controller design for sampled-data nonlinear systems via their approximate discrete-time models. An application of the theorem to establishing uniform asymptotic stability of systems controlled by model reference adaptive controllers designed via approximate discrete-time plant models is presented.     

Multiscale nonlinear decomposition: the sieve decomposition theorem

Sieves decompose one dimensional bounded functions (d_m) _m=1^R that represent the information in a manner that is analogous to the pyramid of wavelets obtained by linear decomposition. Sieves based on sequences of increasing scale open-closings with flat structuring elements (M and N filters) map f to {d} and the recomposition, consisting of adding up all the granule functions, maps {d} to f. Experiments show that a more general property exists such that {dˆ} maps to fˆ and back to {dˆ} where the granule functions {dˆ} are obtained from {d} by applying any operator α consisting of changing the amplitudes of some granules, including zero, without changing their signs. In other words, the set of granule function vectors produced by the decomposition is closed under the operation α. An analytical proof of this property is presented. This property means that filters are useful in the context of feature recognition and, in addition, opens the way for an analysis of the noise resistance of sieves     

Using the VIRT programming language for automatic theorem proving

The expressiveness of the VIRT programming language from the viewpoint of theorem proving is discussed. A program of unit binary resolution is proposed. A comparative analysis of the programming languages VIRT and Lisp is performed. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 87–99, November–December, 1999.     

An adaptive parallel algorithm for finite language decomposition

The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L₁ and L₂ such that L = L₁L₂. Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions L₁L₂ of L. The algorithm is based on an exhaustive search and incorporates several original methods for pruning the search space. Moreover, the algorithm is adaptive since it changes its behavior based on the runtime acquired data related to its performance. Comprehensive computational experiments on more than 4000 benchmark languages generated over alphabets of various sizes have been carried out. The experiments showed that by using the power of parallel computing the decompositions of languages containing more than 200000 words can be found. Decompositions of languages of that size have not been reported in the literature so far.

     

Representations of the language recognition problem for a theorem prover

Two representations of the language recognition problem for a theorem prover in first-order logic are presented and contrasted. One of the representations is based on the familiar method of generating sentential forms of the language, and the other is based on the Cocke parsing algorithm. An augmented theorem prover is described which permits recognition of recursive languages. The state-transformation method developed by Cordell Green to construct problem solutions in resolution-based systems can be used to obtain the parse tree. In particular, the end-order traversal of the parse tree is derived in one of the representations. The paper defines an inference system, termed the cycle inference system, which makes it possible for the theorem prover to model the method on which the representation is based. The general applicability of the cycle inference system to state-space problems is discussed. Given an unsatisfiable setS, where each clause has at most one positive literal, it is shown that there exists an input proof. The clauses for the two representations satisfy these conditions, as do many state-space problems.This work was supported by the National Aeronautics and Space Administration Grant NGR-21-002-270.     

V-Pascal: An automatic vectorizing compiler for Pascal with no language extensions

An automatic vectorizing compiler called V-Pascal is described in detail. The compiler has been designed and implemented with a view to vectorizing Pascal source programs. Using the mechanism of vector indirect addressing, it reduces multiply nestedfor loops to equivalent single loops, which are then executed by vector mode with sufficiently long vector lengths. TheD matrix, which is an adjacency matrix giving dependences between intermediate code nodes, plays an important role in the V-Pascal compiler. It is demonstrated that, in some cases, the V-Pascal compiler yields object code that runs faster than the Fortran counterpart. This paper mainly presents the basic constituents of the Version 1 of the V-Pascal compiler. Version 2 includes higher functions such as vectorization ofwhile-do loops and recursive procedures, vectorization of character string manipulations and relational database operations (written in Pascal), and automatic parallel decomposition for multiprocessor environments.     

XCML: providing context-aware language extensions for the specification of multi-device web applications

There is a vast body of research dealing with the development of context-aware web applications that can adapt to different user, platform and device contexts. However, the range and growing diversity of new devices poses two significant problems to existing approaches. First, many techniques require a number of additional design processes and modelling steps before applications can be adapted. Second, the new generation of platforms and technologies underlying these devices as well as upcoming web standards HTML5 and CSS3 have partly changed the way in which web applications are implemented nowadays and often limit the way in which they can be adapted. In this paper, we present XCML as one example of a domain-specific language that tightly integrates context-aware concepts and adaptivity mechanisms to support developers in the specification and implementation of multi-channel web applications. In contrast to most existing approaches, the objective is to use a more lightweight approach to adaptation that can dynamically evolve and support new requirements as they emerge. Our solution builds on versioning principles in combination with a context matching process based on a declaration of context-dependent variants of content, navigation and presentation in terms of context expressions at different levels of granularity that are specific to the application. To support this, a formally defined context algebra is used to parse and resolve the context expressions at compile-time and to determine the best-matching variants with respect to the client context at run-time. We present the language concepts and a possible execution environment together with context-aware developer tools for the authoring and testing of adaptive features and behaviour. We also report on two case studies: the first shows how our general approach allows for integration with existing technologies to leverage advanced context-aware mechanisms in applications developed using other platforms and languages and the second how existing web interfaces can be systematically extended to support new adaptation scenarios.     

Modelling families of business process variants: A decomposition driven method

Business processes usually do not exist as singular entities that can be managed in isolation, but rather as families of business process variants. When modelling such families of variants, analysts are confronted with the choice between modelling each variant separately, or modelling multiple or all variants in a single model. Modelling each variant separately leads to a proliferation of models that share common parts, resulting in redundancies and inconsistencies. Meanwhile, modelling all variants together leads to less but more complex models, thus hindering on comprehensibility. This paper introduces a method for modelling families of process variants that addresses this trade-off. The key tenet of the method is to alternate between steps of decomposition (breaking down processes into sub-processes) and deciding which parts should be modelled together and which ones should be modelled separately. We have applied the method to two case studies: one concerning the consolidation of existing process models, and another dealing with green-field process discovery. In both cases, the method produced fewer models with respect to the baseline and reduced duplicity by up to 50% without significant impact on complexity.     

Yet another proof of the cascade decomposition theorem for finite automata

We give here a short proof that each finite automaton can be built as a cascade of permutation automata and identity-reset automata.This paper was presented at the Conference on the Algebraic Theory of Machines, Languages and Semigroups, 29 August–8 September 1966, at Asilomar, California, organized by the Krohn-Rhodes Research Institute.     

Program entanglement,feature interaction and the feature language extensions

One of the most difficult tasks in software development is that the programmer must implement a feature going through a laborious and error prone process of modifying the programs of other features. The programs of the different features entangle in the same reusable program units of the programming language, making them also difficult to be verified, maintained and reused. We show that if (C1) the features interact, (C2) they are executed by the same process and (C3) they are implemented in a programming language that requires the programmer to specify execution flows, program entanglement is inevitable and the problem cannot be solved by software design alone. Applications with interacting features are common including those that require exception handling.The feature language extensions (FLX) is a set of programming language constructs designed to enable the programmer to develop interacting features as separate and reusable program modules even though the features interact. The programmer uses FLX to specify non-procedural program units, organize the program units into reusable features and integrate features into executable feature packages. He develops a feature based on a model instead of the code of other features. FLX supports an automatic procedure to detect the interaction condition among features; the programmer then resolve the interaction in a feature package without changing feature code. FLX features and feature packages are reusable; the programmer may package different combinations of them and resolve their interactions differently to meet different user needs. An FLX to Java compiler has been implemented; our experience of using it has been very positive.     

Generalized language measure families of probabilistic finite state systems

The signed real measure of regular languages has been introduced and validated in recent literature for quantitative analysis of discrete-event systems. This paper reports generalizations of the language measure, which can serve as performance indices for synthesis of optimal discrete-event supervisory decision and control laws. These generalizations eliminate a user-selectable parameter in the original concept of language measure. The concepts are illustrated with simple examples.     

A theorem for locating eigenvalues

The primary conclusion derived in this paper is that the leading principal minors of matrixB-ωA (whereB is a symmetric positive definite matrix andA is Hermite matrix) have properties similar to those of Sturm sequences, which is the theoretical basis of the Determinant Search Method for solving the eigenvalue-problem of damped structural systems [1]–[5], correcting the errors in a statement given by K. K. Gupta in [1]–[5].