On transformations of formal power series

Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve recognizability, generalizing the recent results of Zhang [16] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves recognizability for formal power series when the underlying semiring is commutative or locally finite, but not in general.     

The equality problem for Parikh simple algebraic power series

A power series r with noncommuting variables is called Parikh simple if no two words in the support of r are commutatively equivalent. We show that equality is decidable for Parikh simple algebraic power series having their coefficients in a computable field.     

Realization theory for linear switched systems: Formal power series approach

The paper deals with the realization theory of linear switched systems. Necessary and sufficient conditions are formulated for a family of input–output maps to be realizable by linear switched systems. Characterization of minimal realizations is presented. The paper treats two types of linear switched systems. The first one is when all switching sequences are allowed. The second one is when only a subset of switching sequences is admissible, but within this restricted set the switching times are arbitrary. The paper uses the theory of formal power series to derive the results on realization theory.     

Skew and infinitary formal power series

We investigate finite-state systems with weights. Departing from the classical theory, in this paper the weight of an action does not only depend on the state of the system, but also on the time when it is executed; this reflects the usual human evaluation practices in which later events are considered less urgent and carry less weight than close events. We first characterize the terminating behaviors of such systems in terms of rational formal power series. This generalizes a classical result of Schützenberger.     

A formal semantics of SMIL: a web standard to describe multimedia documents

This paper presents a formal semantics of a subset of SMIL2.0: a W3C recommendation to describe interactive multimedia documents on the Web. This work has been used during the design of this standard to improve its consistency. It is also intended to help SMIL developers to understand the specification. Doing so, it will contribute to increase SMIL chances of success in achieving the interoperability goal and, thus, its impact on the new information society.     

A formal approach to object-oriented databases

Object-oriented database systems are the focus of current research and development efforts. Yet, there is no commonly accepted object model, nor is it clear whether such a model can be developed. This paper reports on efforts to develop a formal framework that contains most features found in current object oriented database systems. The framework contains two parts. The first is a structural object model, including concepts such as structured objects, identity, and some form of inheritance. For this model, we explain the distinction between values and (abstract) objects, describe a system as a directed graph, and discuss declarative languages. The second part deals with higher-order concepts, such as classes and functions as data, methods, and inheritance. This part is a sketch, and leaves many issues unresolved. Throughout the paper, the emphasis is on logic-oriented modeling.     

QoS contract preservation through dynamic reconfiguration: A formal semantics approach

The increasing pervasiveness of computing services in everyday life, combined with the dynamic nature of their execution contexts, constitutes a major challenge in guaranteeing the expected quality of such services at runtime. Quality of Service (QoS) contracts have been proposed to specify expected quality levels (QoS levels) on different context conditions, with different enforcing mechanisms. In this paper we present a definition for QoS contracts as a high-level policy for governing the behavior of software systems that self-adapt at runtime in response to context changes. To realize this contract definition, we specify its formal semantics and implement it in a software framework able to execute and reconfigure software applications, in order to maintain fulfilled their associated QoS contracts. The contribution of this paper is threefold. First, we extend typed-attributed graph transformation systems and finite-state machines, and use them as denotations to specify the semantics of QoS contracts. Second, this semantics makes it possible to systematically exploit design patterns at runtime by dynamically deploying them in the managed software application. Third, our semantics guarantees self-adaptive properties such as reliability and robustness in the contract satisfaction. Finally, we evaluate the applicability of our semantics implementation by integrating and executing it in FraSCAti, a multi-scale component-based middleware, in three case studies.     

Process time patterns: A formal foundation

Companies increasingly adopt process-aware information systems (PAISs) to model, execute, monitor, and evolve their business processes. Though the handling of temporal constraints (e.g., deadlines or time lags between activities) is crucial for the proper support of business processes, existing PAISs vary significantly regarding the support of the temporal perspective. Both the formal specification and the operational support of temporal constraints constitute fundamental challenges in this context. In previous work, we introduced process time patterns, which facilitate the comparison and evaluation of PAISs in respect to their support of the temporal perspective. Furthermore, we provided empirical evidence for these time patterns. To avoid ambiguities and to ease the use as well as the implementation of the time patterns, this paper formally defines their semantics. To additionally foster the use of the patterns for a wide range of process modeling languages and to enable pattern integration with existing PAISs, the proposed semantics are expressed independently of a particular process meta model. Altogether, the presented pattern formalization will be fundamental for introducing the temporal perspective in PAISs.     

A compound class of Weibull and power series distributions

In this paper we introduce the Weibull power series (WPS) class of distributions which is obtained by compounding Weibull and power series distributions, where the compounding procedure follows same way that was previously carried out by Adamidis and Loukas (1998). This new class of distributions has as a particular case the two-parameter exponential power series (EPS) class of distributions (Chahkandi and Ganjali, 2009), which contains several lifetime models such as: exponential geometric (Adamidis and Loukas, 1998), exponential Poisson (Kus, 2007) and exponential logarithmic (Tahmasbi and Rezaei, 2008) distributions. The hazard function of our class can be increasing, decreasing and upside down bathtub shaped, among others, while the hazard function of an EPS distribution is only decreasing. We obtain several properties of the WPS distributions such as moments, order statistics, estimation by maximum likelihood and inference for a large sample. Furthermore, the EM algorithm is also used to determine the maximum likelihood estimates of the parameters and we discuss maximum entropy characterizations under suitable constraints. Special distributions are studied in some detail. Applications to two real data sets are given to show the flexibility and potentiality of the new class of distributions.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

Partial-realization theory for linear switched systems —A formal power series approach

The paper presents partial-realization theory and a realization algorithm for linear switched systems. The results are similar to partial-realization theory of linear and bilinear systems. Our main tool is the theory of rational formal power series.     

A symbolic summation approach to Feynman integral calculus

Given a Feynman parameter integral, depending on a single discrete variable N$N$ and a real parameter ε$\epsilon$, we discuss a new algorithmic framework to compute the first coefficients of its Laurent series expansion in ε$\epsilon$. In a first step, the integrals are expressed by hypergeometric multi-sums by means of symbolic transformations. Given this sum format, we develop new summation tools to extract the first coefficients of its series expansion whenever they are expressible in terms of indefinite nested product–sum expressions. In particular, we enhance the known multi-sum algorithms to derive recurrences for sums with complicated boundary conditions, and we present new algorithms to find formal Laurent series solutions of a given recurrence relation.     

Nature-inspired computation and communication: A formal approach

We introduce the special issue with the title of “Nature-inspired Computation and Communication: A Formal Approach” edited by Prof. Phan Cong Vinh and Dr. Emil Vassev to scientists, researchers, professionals and students in the field of computing. Hopefully, they will find this issue provoking for their research related to hot topics of computing and being useful to their future work.     

A Faà di Bruno Hopf algebra for a group of Fliess operators with applications to feedback

A Faà di Bruno type Hopf algebra is developed for a group of integral operators known as Fliess operators, where operator composition is the group product. Such operators are normally written in terms of generating series over a noncommutative alphabet. Using a general series expansion for the antipode, an explicit formula for the generating series of the compositional inverse operator is derived. The result is applied to analytic nonlinear feedback systems to produce an explicit formula for the feedback product, that is, the generating series for the Fliess operator representation of the closed-loop system written in terms of the generating series of the Fliess operator component systems. This formula is employed to provide a proof that local convergence is preserved under feedback.     

Polarization of forecast densities: A new approach to time series classification

Time series classification has been extensively explored in many fields of study. Most methods are based on the historical or current information extracted from data. However, if interest is in a specific future time period, methods that directly relate to forecasts of time series are much more appropriate. An approach to time series classification is proposed based on a polarization measure of forecast densities of time series. By fitting autoregressive models, forecast replicates of each time series are obtained via the bias-corrected bootstrap, and a stationarity correction is considered when necessary. Kernel estimators are then employed to approximate forecast densities, and discrepancies of forecast densities of pairs of time series are estimated by a polarization measure, which evaluates the extent to which two densities overlap. Following the distributional properties of the polarization measure, a discriminant rule and a clustering method are proposed to conduct the supervised and unsupervised classification, respectively. The proposed methodology is applied to both simulated and real data sets, and the results show desirable properties.     

From individuals to populations: A mean field semantics for process algebra

A new semantics in terms of mean field equations is presented for WSCCS (Weighted Synchronous Calculus of Communicating Systems). The semantics captures the average behaviour of the system over time, but without computing the entire state space, therefore avoiding the state space explosion problem. This allows easy investigation of models with large numbers of components. The new semantics is shown to be equivalent to the standard Discrete Time Markov Chain semantics of WSCCS as the number of processes tends to infinity. The method of deriving the semantics is illustrated with examples drawn from biology and from computing.     

A multisensor fusion approach to improve LAI time series

High-quality and gap-free satellite time series are required for reliable terrestrial monitoring. Moderate resolution sensors provide continuous observations at global scale for monitoring spatial and temporal variations of land surface characteristics. However, the full potential of remote sensing systems is often hampered by poor quality or missing data caused by clouds, aerosols, snow cover, algorithms and instrumentation problems. A multisensor fusion approach is here proposed to improve the spatio-temporal continuity, consistency and accuracy of current satellite products. It is based on the use of neural networks, gap filling and temporal smoothing techniques. It is applicable to any optical sensor and satellite product. In this study, the potential of this technique was demonstrated for leaf area index (LAI) product based on MODIS and VEGETATION reflectance data. The FUSION product showed an overall good agreement with the original MODIS LAI product but exhibited a reduction of 90% of the missing LAI values with an improved monitoring of vegetation dynamics, temporal smoothness, and better agreement with ground measurements.     

A passivity approach to game-theoretic CDMA power control

This paper follows a game-theoretical formulation of the CDMA power control problem and develops new decentralized control algorithms that globally stabilize the desired Nash equilibrium. The novel approach is to exploit the passivity properties of the feedback loop comprising the mobiles and the base station. We first reveal an inherent passivity property in an existing gradient-type algorithm, and prove stability from the Passivity Theorem. We then exploit this passivity property to develop two new designs. In the first design, we extend the base station algorithm with Zames-Falb multipliers which preserve its passivity properties. In the second design, we broaden the mobile power update laws with more general, dynamic, passive controllers. These new designs may be exploited to enhance robustness and performance, as illustrated with a realistic simulation study. We then proceed to show robustness of these algorithms against time-varying channel gains.