QFT template generation for time-delay plants based on zero-inclusion test

Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ⁻,τ⁺], qQ∏_k=0^m−1[q_k⁻,q_k⁺]}, where f(τ,q)=g(q)+h(q)e^−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω^* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2^m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included.     

Riccati equations and normalized coprime factorizations for strongly stabilizable infinite-dimensional systems

The first part of the paper concerns the existence of strongly stabilizing solutions to the standard algebraic Riccati equation for a class of infinite-dimensional systems of the form Σ(A,B,S^−1/2B^*,D), where A is dissipative and all the other operators are bounded. These systems are not exponentially stabilizable and so the standard theory is not applicable. The second part uses the Riccati equation results to give formulas for normalized coprime factorizations over H_∞ for positive real transfer functions of the form D+S^−1/2B^*(author−A)⁻¹,B.     

An algorithm for the con due-date determination and sequencing problem

For a set of n jobs with deterministic processing times and common starting times, the problem is to determine the optimal constant flow allowance k^* for the CON due-date assignment method and the optimal sequence σ^* which minimizes the weighted average of missed due-dates. As k^* and σ^* cannot be independently determined, we propose an algorithm which systematically searches for the optimal solution. Although the algorithm has time complexity of 0(2ⁿn²), it is considerably more efficient than the exhaustive enumeration method which considers all n! possible sequences.     

The Expressive Power of Finitely Many Generalized Quantifiers

We consider extensions of first order logic (FO) and fixed point logic (FP) by means of generalized quantifiers in the sense of Lindström. We show that adding a finite set of such quantifiers to FP fails to capture PTIME, even over a fixed signature, strengthening earlier results. We also prove a stronger version of this result for PSPACE, which enables us to establish that PSPACE ≠ FO on any infinite class of ordered structures, a weak version of the ordered conjecture formulated by Ph. G. Kolaitis and M. Y. Vardi (Fixpoint logic vs. infinitary logic in finite-model theory, in "Proceedings, 7th IEEE Symposium on Logic in Computer Science, 1992," pp. 46-57). These results are obtained by defining a notion of element type for bounded variable logics with finitely many generalized quantifiers. Using these, we characterize the classes of finite structures over which the infinitary logic L^ω_∞ω extended by a finite aw set of generalized quantifiers Q is no more expressive than first order logic extended by the quantifiers in Q.     

State-oriented Noninterference for CCS

We address the question of typing noninterference (NI) in the calculus CCS, in such a way that Milner's translation into CCS of a standard parallel imperative language preserves both an existing NI property and the associated type system. Recently, Focardi, Rossi and Sabelfeld have shown that a variant of Milner's translation, restricted to the sequential fragment of the language, maps a time-sensitive NI property to that of Persistent Bisimulation-based Non Deducibility on Compositions (PBNDC) on CCS. However, since CCS was not equipped with a type system, the question of whether the translation preserves types could not be addressed. We extend Focardi, Rossi and Sabelfeld's result by showing that a slightly simpler variant of Milner's translation preserves a time-insensitive NI property on the full parallel language, by mapping it again to PBNDC. As a by-product, we formalise a folklore result, namely that Milner's translation preserves a behavioural equivalence on programs. We present a simple type system ensuring PBNDC on CCS, inspired by existing type systems for the π-calculus. Unfortunately, this type system as it stands is too restrictive to grant the expected type preservation result. We sketch a solution to overcome this problem.     

Congruence of Bisimulation in a Non-Deterministic Call-By-Need Lambda Calculus

We present a call-by-need λ-calculus λ_ND with an erratic non-deterministic operator pick and a non-recursive let. A definition of a bisimulation is given, which has to be based on a further calculus named λ_≈, since the naïve bisimulation definition is useless. The main result is that bisimulation in λ_≈ is a congruence and coincides with the contextual equivalence. The proof is a non-trivial extension of Howe's method. This might be a step towards defining useful bisimulation relations and proving them to be congruences in calculi that extend the λ_ND-calculus.     

Branching-Depth Hierarchies

We study the distinguishing and expressive power of branching temporal logics with bounded nesting depth of path quantifiers. We define the fragments CTL^*_i and CTL_i of CTL^* and CTL, where at most i nestings of path quantifiers are allowed. We show that for all i ≥ 1, the logic CTL^*_i+1 has more distinguishing and expressive power than CTL^*_i; thus the branching-depth hierarchy is strict. We describe equivalence relations H_i that capture CTL^*_i: two states in a Kripke structure are H_i-equivalent iff they agree on exactly all CTL^*_i formulas. While H₁ corresponds to trace equivalence, the limit of the sequence H₁, H₂,… is Milner's bisimulation. These results are not surprising, but they give rise to several interesting observations and problems. In particular, while CTL^* and CTL have the same distinguishing power, this is not the case for CTL^*_i and CTL_i. We define the branching depth of a structure as the minimal index i for which H_i+1=H_i. The branching depth indicates on the possibility of using bisimulation instead of trace equivalence (and similarly for simulation and trace containment). We show that the problem of finding the branching depth is PSPACE-complete.     

Approximation by Bézier type of Meyer–König and Zeller operators

In this paper, we give direct, inverse and equivalence approximation theorems for the Bézier type of Meyer–König and Zeller operator with unified Ditzian–Totik modulus ω_φ^λ(f,t) (0≤λ≤1).     

The super spanning connectivity and super spanning laceability of the enhanced hypercubes

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k ^* -container if it contains all vertices of G. A graph G is k ^* -connected if there exists a k ^*-container between any two distinct vertices of G. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k ^*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k ^* -laceable if there exists a k ^*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k ^*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q _n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

On the connection between the exponential stability of C0-semigroups and the admissibility of a certain Sobolev space

Let T be a strongly continuous semigroup on a Banach space X and A its infinitesimal generator. We will prove that T is exponentially stable, if and only if, there exist p[1,∞) such that the space is admissible to the system Σ(A,I,I), defined below (i.e for all f belonging to the Sobolev space the convolution T*f lies in .     

Conjunctions of Unate DNF Formulas: Learning and Structure

A central topic in query learning is to determine which classes of Boolean formulas are efficiently learnable with membership and equivalence queries. We consider the class ^kconsisting of conjunctions ofkunate DNF formulas. This class generalizes the class ofk-clause CNF formulas and the class of unate DNF formulas, both of which are known to be learnable in polynomial time with membership and equivalence queries. We prove that ²can be properly learned with a polynomial number of polynomial-size membership and equivalence queries, but can be properly learned in polynomial time with such queries if and only if P=NP. Thus the barrier to properly learning ²with membership and equivalence queries is computational rather than informational. Few results of this type are known. In our proofs, we use recent results of Hellersteinet al.(1997,J. Assoc. Comput. Mach.43(5), 840–862), characterizing the classes that are polynomial-query learnable, together with work of Bshouty on the monotone dimension of Boolean functions. We extend some of our results to ^kand pose open questions on learning DNF formulas of small monotone dimension. We also prove structural results for ^k. We construct, for any fixedk2, a class of functionsfthat cannot be represented by any formula in ^k, but which cannot be “easily” shown to have this property. More precisely, for any functionfonnvariables in the class, the value offon any polynomial-size set of points in its domain is not a witness thatfcannot be represented by a formula in ^k. Our construction is based on BCH codes.     

Towards coalgebraic behaviourism

In this paper we show that it is possible to model observable behaviour of coalgebras independently from their internal dynamics, but within the general framework of representing behaviour by a map into a “final” coalgebra.In the first part of the paper we characterise Set-endofunctors F with the property that bisimilarity of elements of F-coalgebras coincides with having the same observable behaviour. We show that such functors have the final coalgebra of a rather simple nature, and preserve some weak pullbacks. We also show that this is the case if and only if F-bisimilarity corresponds to logical equivalence in the finitary fragment of the coalgebraic logic.In the second part of the paper, we present a construction of a “final” coalgebra that captures the observable behaviour of F-coalgebras. We keep the word “final” quoted since the object we are going to construct need not belong to the original category. The construction is carried out for arbitrary Set-endofunctor F, throughout the construction we remain in Set, but the price to pay is the introduction of new morphisms. The paper concludes with a hint to a possible application to modelling weak bisimilarity for coalgebras.     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Adding Action Refinement to a Finite Process Algebra

In this paper we present a Process Algebra for the specification of concurrent, communicating processes which incorporates operators for the refinement of actions by processes, in addition to the usual operators for communication, nondeterminism, internal actions, and restrictions, and study a suitable notion of semantic equivalence for it. We argue that action refinements should not, in some formal sense, interfere with the internal evolution of processes and their application to processes should consider the restriction operator as a "binder." We show that, under the above assumptions, the weak version of the refine equivalence introduced by Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269) is preserved by action refinements and, moreover, is the largest such equivalence relation contained in weak bismulation equivalence. We also discuss an example showing that, contrary to what happens in Aceto and Hennessy ((1993) Inform. and Comput.103, 204-269), refine equivalence and timed equivalence are different notions of equivalence over the language considered in this paper.     

Robust stabilization of infinite dimensional systems by finite dimensional controllers

The problem of robustly stabilizing an infinite dimensional system with transfer function G, subject to an additive perturbation Δ is considered. It is assumed that: G ε ₀(σ) of systems introduced by Callier and Desoer [3]; the perturbation satisfies |W₁ΔW₂| < ε, where W₁ and W₂ are stable and minimum phase; and G and G + Δ have the same number of poles in ⁺. Now write W₁GW₂=G₁ + G₁, where G₁ is rational and totally unstable and G₂ is stable. Generalizing the finite dimensional results of Glover [12] this family of perturbed systems is shown to be stabilizable if and only if ε σ_min (G^*₁)( = the smallest Hankel singular value of G^*₁). A finite dimensional stabilizing controller is then given by where 2 is a rational approximation of G₂ such that

Full-size image

) and K₁ robustly stabilizes G₁ to margin ε. The feedback system (G, K) will then be stable if |W₁ΔW₂| _∞< ε − Δ.     

Projective Linear Groups as Galois Groups overQvia Modular Representations

We give an algorithm for the determination of the finitely many primes such that the image of the modular Galois representations attached to a weight 2 newform on Γ₀(N) without complex multiplication or inner twists may not be “as large as possible". We apply the algorithm to suitable newforms and we obtain the realization of the groups PSL(2,F_ℓ²),PGL (2,F_ℓ³) andPSL (2,F_ℓ⁴) as Galois groups overQfor high density sets of primes.     

The mean-shift outlier model in general weighted regression and its applications

Consider the general weighted linear regression model y=Xβ+, where E()=0, Cov()=Vσ², σ² is an unknown positive scalar, and V is a symmetric positive-definite matrix not necessary diagonal. Two models, the mean-shift outlier model and the case-deletion model, can be employed to develop multiple case-deletion diagnostics for the linear model. The multiple case-deletion diagnostics are obtained via the mean-shift outlier model in this article and are shown to be equivalent to the deletion diagnostics via the case deletion model obtained by Preisser and Qaqish (1996, Biometrika, 83, 551–562). In addition, computing the multiple case-deletion diagnostics obtained via the mean-shift outlier model is faster than computing the one based on the more commonly used case-deletion model in some situations. Applications of the multiple deletion diagnostics developed from the mean-shift outlier model are also given for regression analysis with the likelihood function available and regression analysis based on generalized estimating equations. These applications include survival models and the generalized estimating equations of Liang and Zeger (1986, Biometrika, 73, 13–22). Several numerical experiments as well as a real example are given as illustrations.     

Involution codes: with application to DNA coded languages

For an involution θ : Σ^* → Σ^* over a finite alphabet Σ we consider involution codes: θ-infix, θ-comma-free, θ-k -codes and θ-subword-k-codes. These codes arise from questions on DNA strand design. We investigate conditions under which both X and X⁺ are same type of involution codes. General methods for generating such involution codes are given. The information capacity of these codes show to be optimized in most cases. A specific set of these codes was chosen for experimental testing and the results of these experiments are presented.     

Infinitary Logic and Inductive Definability over Finite Structures

The extensions of first-order logic with a least fixed point operator (FO + LFP) and with a partial fixed point operator (FO + PFP) are known to capture the complexity classes P and PSPACE respectively in the presence of an ordering relation over finite structures. Recently, Abiteboul and Vianu (in "Proceedings of the 23rd ACM Symposium on the Theory of Computing," 1991) investigated the relationship of these two logics in the absence of an ordering, using a machine model of generic computation. In particular, they showed that the two languages have equivalent expressive power if and only if P = PSPACE. These languages can also be seen as fragments of an infinitary logic where each formula has a bounded number of variables, L^ω_∞ω, (see, for instance, Kolaitis and Vardi, in "Proceedings of the 5th IEEE Symposium on Logic in Computer Science," pp. 156-167, 1990). We investigate this logic on finite structures and provide a normal form for it. We also present a treatment of Abiteboul and Vianu′s results from this point of view. In particular, we show that we can write a formula of FO + LFP that defines an ordering of the L^k_∞ω, types uniformly over all finite structures. One consequence of this is a generalization of the equivalence of FO + LFP and P from ordered structures to classes of structures where every element is definable. We also settle a conjecture mentioned by Abiteboul and Vianu by showing that FO + LFP is properly contained in the polynomial time computable fragment of L^ω_∞ω, raising the question of whether the latter fragment is a recursively enumerable class.     

Comonoids in chu: a large cartesian closed sibling of topological spaces

Com_K may be defined as the (cartesian closed) category of comonoids in chu_K, or equivalently as dictionaries D for which any crossword over D has its main diagonal in D. Com₂ resembles Top, ordinary topological spaces. Common to both are the Alexandroff posets and the Scott DCPOs, while the topological space and the dual DCPO {−∞ < … < −2 < −1 < 0} jointly witness the incomparability of Com₂ and Top. Such comonoids support a notion of bitopology admitting limits simultaneously for convergence and divergence. We raise the questions of whether a comonoid in chu₂ can be fully specified in terms of its specialization order and omitted cuts, and which cuts are optional. These questions have been actively pursued for four weeks as of this writing on the theory-edge mailing list in response to Puzzle 1.5 starting with http://groups.yahoo.com/group/theory-edge/messages/6957.