From Varieties of Algebras to Covarieties of Coalgebras

Varieties of F-algebras with respect to an endofunctor F on an arbitrary cocomplete category C are defined as equational classes admitting free algebras. They are shown to correspond precisely to the monadic categories over C. Under suitable assumptions satisfied in particular by any endofunctor on Set and Set^op the Birkhoff Variety Theorem holds. By dualization, covarieties over complete categories C are introduced, which then correspond to the comonadic categories over C, and allow for a characterization in dual terms of the Birkhoff Variety Theorem. Moreover, the well known conditions of accessibilitly and boundedness for Set-functors F, sufficient for the existence of cofree F-coalgebras, are shown to be equivalent.     

Coalgebraic Semantics for Positive Modal Logic

Positive Modal Logic is the restriction of the modal local consequence relation defined by the class of all Kripke models to the propositional negation-free modal language. The class of positive modal algebras is the one canonically associated with PML according to the theory of the algebraization of logics. In [4], a Priestley-style duality is established between the category of positive modal algebras and the category of K⁺-spaces. In this paper, we establish a categorical equivalence between the category K⁺ of K⁺-spaces and the category Coalg(V) of coalgebras of a suitable endofunctor V on the category of Priestley spaces.     

Sample complexity of worst-case H-identification

We show that the sample complexity of qorst-case H^∞-identification is of order n², by proving that the minimal length of a fractional H^∞-cover for C_n, regarded as the linear space of complex-valued sequences of length n, is of order n². A unit vector u in ^∞ is a fractional H^∞-cover for C_n if for some

Full-size image

for all rh ε C_n, where is the z-transform of h. We also give similar results for real-valued sequences.     

A Coalgebraic View of Infinite Trees and Iteration

The algebra of infinite trees is, as proved by C. Elgot, completely iterative, i.e., all ideal recursive equations are uniquely solvable. This is proved here to be a general coalgebraic phenomenon: let H be an endofunctor such that for every object X a final coalgebra, TX, of H(_) + X exists. Then TX is an object-part of a monad which is completely iterative. Moreover, a similar contruction of a “completely iterative monoid” is possible in every monoidal category satisfying mild side conditions.     

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.     

Infinitary logics and 0–1 laws

We investigate the infinitary logic L_∞ω^ω, in which sentences may have arbitrary disjunctions and conjunctions, but they involve only finite numbers of distinct variables. We show that various fixpoint logics can be viewed as fragments of L_∞ω^ω, and we describe a game-theoretic characterization of the expressive power of the logic. Finally, we study asymptotic probabilities of properties expressible in L_∞ω^ω on finite structures. We show that the 0–1 law holds for L_∞ω^ω, i.e., the asymptotic probability of every sentence in this logic exists and is equal to either 0 or 1. This result subsumes earlier work on asymptotic probabilities for various fixpoint logics and reveals the boundary of 0–1 laws for infinitary logics.     

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.     

On improving control-loop robustness of model-matching controllers

This note first characterizes the class of all stabilizing controllers for a two-degree-of-Freedom control system which achieve a prescribed achievable transfer function. The characterization is in terms of an arbitrary proper stable transfer function. With this characterization, robust model matching is formulated as a standard H^∞-optimization problem. This means that standard controller designs for a nominal plant, such as linear-quadratic Gaussian ones, can be enhanced to give improved robustness properties using H^∞-design techniques.     

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.     

Synthesis of stable H controller via the chain scattering framework

A sufficient condition for the existence of suboptimal stable stabilizing H^∞ controllers is given. By exploiting the free parameter in the parameterization of stabilizing controllers and using the chain scattering framework, we reformulate the H^∞ strong stabilization problem as an equivalent H^∞ optimization problem which can be solved via only one algebraic Riccati equation. A parameterization of all suboptimal stable stabilizing H^∞ controllers is also given.     

Stabilization and H control of symmetric systems: an explicit solution

In this paper we address the H^∞ control analysis, the output feedback stabilization, and the output feedback H^∞ control synthesis problems for state-space symmetric systems. Using a particular solution of the Bounded Real Lemma for an open-loop symmetric system we obtain an explicit expression to compute the H^∞ norm of the system. For the output feedback stabilization problem we obtain an explicit parametrization of all asymptotically stabilizing control gains of state-space symmetric systems. For the H^∞ control synthesis problem we derive an explicit expression for the optimally achievable closed-loop H^∞ norm and the optimal control gains. Extension to robust and positive real control of such systems are also examined. These results are obtained from the linear matrix inequality formulations of the stabilization and the H^∞ control synthesis problems using simple matrix algebraic tools.     

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.     

On the weighted sensitivity minimization problem for delay systems

We consider the H^∞-optimal sensitivity problem for delay systems. In particular, we consider computation of μ:= inf {|W-φq|_∞ : q ε H^∞(j )} where W(s) is any function in RH^∞(j ), and φ in H^∞(j ) is any inner function. We derive a new explicit solution in the pure delay case where φ = e^−sh, h > 0.     

Adaptive λ-tracking for a class of infinite-dimensional systems

For a class of high-gain stabilizable multivariable linear infinite-dimensional systems we present an adaptive control law which achieves approximate asymptotic tracking in the sense that the tracking error tends asymptotically to a ball centred at 0 and of arbitrary prescribed radius λ>0. This control strategy, called λ-tracking, combines proportional error feedback with a simple nonlinear adaptation of the feedback gain. It does not involve any parameter estimation algorithms, nor is it based on the internal model principle. The class of reference signals is W^1,∞, the Sobolev space of absolutely continuous functions which are bounded and have essentially bounded derivative. The control strategy is robust with respect to output measurement noise in W^1,∞ and bounded input disturbances. We apply our results to retarded systems and integrodifferential systems.     

An alternative solution to the H∞-optimal control problem

In this paper we present an alternative solution to the problem min _{X ε H^n×n∞} |A + BXC|_∞ where A, B, rmand C are rational matrices in H^n×n_∞. The solution circumvents the need to extract the matrix inner factors of B and C, providing a multivariable extension of Sarason's H^∞-interpolation theory [1] to the case of matrix-valued B(s) and C(s). The result has application to the diagonally-scaled optimization problem int |D(A + BXC)D⁻¹|_∞, where the infimum is over D, X εH^n×n_∞, D diagonal.     

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.     

Some Co-Birkhoff Type Theorems

We consider the dual of Theorem 1 from [33], relating closure conditions on subcategories with projectivity classes for collections of discrete cocones. We extend these results by adding a new operator for closure under domains of epis and show that this corresponds to taking projectivity classes for cocones with vertex a subobject of the terminal object. We show that these theorems apply to categories of coalgebras under reasonable assumptions on the base category and endofunctor. Lastly, we discuss cofree for V coalgebras in this setting and give examples of so-called Horn covarieties of coalgebras.     

Recursive Data Types in Algebraically ω-Complete Categories

A category (of data types) is called algebraically ω-complete provided that for each endofunctor T the data-type equation T(X) X has a solution constructed as a colimit of the ω-chain → T() → T²()..., where is the initial data-type. Examples include the categories of (1) countable sets and (total, partial, or nondeterministic) functions, (2) countably dimensional vector spaces and linear functions, (3) countable well-ordered sets and join-preserving functions. In the case of categories enriched over CPO (the category of complete partial orders and strict, continuous functions) a stronger property holds for all locally continuous functors T: the data-type equation is both a limit and a colimit of the finite iterations of T over the initial data-type.     

Inherent robustness of MRAC schemes

A standard model reference adaptive control (MRAC) scheme without modification of the adaptive law is inherently robust with respect to L^∞ ∩ L² disturbances in the sense that all closed-loop signals remain bounded and the tracking error belongs to L^∞ ∩ L². A MRAC scheme with a new adaptive law is inherently robust with respect to the disturbances in L^∞ ∩ L^1+α, 0 < α < ∞, with an L^1+β tracking error, for .