A comment on “L∞ optimal control of SISO continuous-time systems”

The paper “L_∞ optimal control of SISO continuous-time systems” by Wang and Sznaier (Wang & Sznaier (1997). Automatica, 33 (1), 85–90) studies the problem of designing a controller that optimally minimizes the peak absolute value of system output, due to a fixed input signal. With a newly defined function space A_∞, it was claimed that the set of all L_∞-bounded outputs could be parameterized and that the problem could be transformed to a minimal distance problem on L_∞ space. We believe, however, their formulation has essential flaws.     

Combined super-/substring and super-/subsequence problems

Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of “weak minimal” superstrings and “weak maximal” substrings for which (i) is polynomial-time solvable.     

Boolean operations and inclusion test for attribute–element constraints

The history of schema languages for XML is (roughly) an increase of expressiveness. While early schema languages mainly focused on the element structure, Clark first paid an equal attention to attributes by allowing both element and attribute constraints in a single constraint expression (we call his mechanism “attribute–element constraints”). In this paper, we investigate intersection and difference operations and inclusion test for attribute–element constraints, in view of their importance in static typechecking for XML processing programs. The contributions here are (1) proofs of closure under intersection and difference as well as decidability of inclusion test and (2) algorithm formulations incorporating a “divide-and-conquer” strategy for avoiding an exponential blow-up for typical inputs.     

Finite fuzzy automata, regular fuzzy languages, and pattern recognition

Fuzzy set theory is summarized, and finite fuzzy automata and languages are described. Some results in fuzzy languages based on the “max(min)” rule are discussed. An application of fuzzy languages in syntactic pattern analysis is described and is illustrated by a simple example.     

Discrete-time system modelling in Lp with orthonormal basis functions

In this paper, model sets for linear time-invariant systems spanned by fixed pole orthonormal bases are investigated. The obtained model sets are shown to be complete in L_p(T) (1<p<∞), the Lebesque spaces of functions on the unit circle T, and in C(T), the space of periodic continuous functions on T. The L_p norm error bounds for estimating systems in L_p(T) by the partial sums of the Fourier series formed by the orthonormal functions are computed for the case 1<p<∞. Some inequalities on the mean growth of the Fourier series are also derived. These results have application in estimation and model reduction.     

Expert systems in the context of multi-brain systems

In this article, we postulate the possibility of building a four-brain like expert system. For this purpose we have taken ideas from Minsky’s “Society of Mind” some concepts from Brooks and Stein’s “Brains for Bodies” project, and some mechanisms from neurophysiology. In our search for conceptualization of a minimum multi-brain like system oriented to expert systems, we found that: (a) expert systems with blackboard architecture can be seen as primitive topological approaches to multi-brain systems, (b)in our multi-brain like expert systems conception, as in many other expert systems, we feel that we have to impose our external language as their internal language and our external symbols as their internal symbols. These are the kind of entities discussed by philosophers as “What is it like to be a Bat?”. In this context our conception is still a “Batman”. True-cognitive expert systems might be produced in the future if the matters are self constructed internal languages, and its post-hoc knowledge, and (c) in the scope of multi-brain systems, expert systems are not an engineering subject of artificial intelligence (AI) but a substantive subject that goes from philosophical to neurophysiological aspects.     

Relation-algebraic semantics

The first half is a tutorial on orderings, lattices, Boolean algebras, operators on Boolean algebras, Tarski's fixed point theorem, and relation algebras.

In the second half, elements of a complete relation algebra are used as “meanings” for program statements. The use of relation algebras for this purpose was pioneered by de Bakker and de Roever in [10–12]. For a class of programming languages with program schemes, single μ-recursion, while-statements, if-then-else, sequential composition, and nondeterministic choice, a definition of “correct interpretation” is given which properly reflects the intuitive (or operational) meanings of the program constructs. A correct interpretation includes for each program statement an element serving as “input/output relation” and a domain element specifying that statement's “domain of nontermination”. The derivative of Hitchcock and Park [17] is defined and a relation-algebraic version of the extension by de Bakker [8, 9] of the Hitchcock-Park theorem is proved. The predicate transformers wp_s(-) and wlp_s(-) are defined and shown to obey all the standard laws in [15]. The “law of the excluded miracle” is shown to hold for an entire language if it holds for that language's basic statements (assignment statements and so on). Determinism is defined and characterized for all the program constructs. A relation-algebraic version of the invariance theorem for while-statements is given. An alternative definition of intepretation, called “demonic”, is obtained by using “demonic union” in place of ordinary union, and “demonic composition” in place of ordinary relational composition. Such interpretations are shown to arise naturally from a special class of correct interpretations, and to obey the laws of wp_s(-).     

The “burning ship” and its quasi-Julia sets

By manipulating the imaginary part of the complex-analytic quadratic equation, we obtain, by iteration, a set that we call the “burning ship” because of its appearance. It is an analogue to the Mandelbrot set (M-set). Its nonanalytic “quasi”-Julia sets yield surprizing graphical shapes.     

A modal proof theory for final polynomial coalgebras

An infinitary proof theory is developed for modal logics whose models are coalgebras of polynomial functors on the category of sets. The canonical model method from modal logic is adapted to construct a final coalgebra for any polynomial functor. The states of this final coalgebra are certain “maximal” sets of formulas that have natural syntactic closure properties.

The syntax of these logics extends that of previously developed modal languages for polynomial coalgebras by adding formulas that express the “termination” of certain functions induced by transition paths. A completeness theorem is proven for the logic of functors which have the Lindenbaum property that every consistent set of formulas has a maximal extension. This property is shown to hold if the deducibility relation is generated by countably many inference rules.

A counter-example to completeness is also given. This is a polynomial functor that is not Lindenbaum: it has an uncountable set of formulas that is deductively consistent but has no maximal extension and is unsatisfiable, even though all of its countable subsets are satisfiable.     

A distributed approach for fault detection and diagnosis based on Time Petri Nets

This paper proposes an algorithm for the model based design of a distributed protocol for fault detection and diagnosis for very large systems. The overall process is modeled as different Time Petri Net (TPN) models (each one modeling a local process) that interact with each other via guarded transitions that becomes enabled only when certain conditions (expressed as predicates over the marking of some places) are satisfied (the guard is true). In order to use this broad class of time DES models for fault detection and diagnosis we derive in this paper the timing analysis of the TPN models with guarded transitions. In this paper we also extend the modeling capability of the faults calling some transitions faulty when operations they represent take more or less time than a prescribed time interval corresponding to their normal execution. We consider here that different local agents receive local observation as well as messages from neighboring agents. Each agent estimates the state of the part of the overall process for which it has model and from which it observes events by reconciling observations with model based predictions. We design algorithms that use limited information exchange between agents and that can quickly decide “questions” about “whether and where a fault occurred?” and “whether or not some components of the local processes have operated correctly?”. The algorithms we derive allow each local agent to generate a preliminary diagnosis prior to any communication and we show that after communicating the agents we design recover the global diagnosis that a centralized agent would have derived. The algorithms are component oriented leading to efficiency in computation.     

The structure of a linear chip firing game and related models

In this paper, we study the dynamics of sand grains falling in sand piles. Usually sand piles are characterized by a decreasing integer partition and grain moves are described in terms of transitions between such partitions. We study here four main transition rules. The worst classical one, introduced by Brylawski (Discrete Math. 6 (1973) 201) induces a lattice structure L_B(n) (called dominance ordering) between decreasing partitions of a given integer n. We prove that a more restrictive transition rule, called SPM rule, induces a natural partition of L_B(n) in suborders, each one is associated to a fixed point for the SPM rule. In the second part, we extend the SPM rule in a natural way and obtain a model called Linear Chip Firing Game (Theoret. Comput. Sci. 115 (1993) 321). We prove that this new model has interesting properties: the induced order is a lattice, a natural greedoid can be associated to the model and it also defines a strongly convergent game. In the last section, we generalize the SPM rule in another way and obtain other lattice structure parametrized by some θ, denoted by L(n,θ), which form a decreasing sequence of lattices when θ varies in [−n+2,n]. For each θ, we characterize the fixed point of L(n,θ) and give the value of its maximal sized chain's length. We also note that L(n,−n+2) is the lattice of all compositions of n.     

A Game Theoretic Approach to the Analysis of Dynamic Networks

A model of dynamic networks is introduced which incorporates three kinds of network changes: deletion of nodes (by faults or sabotage), restoration of nodes (by actions of “repair”), and creation of nodes (by actions that extend the network). The antagonism between the operations of deletion and restoration resp. creation is modelled by a game between the two agents “Destructor” and “Constructor”. In this framework of dynamic model-checking, we consider as specifications (“winning conditions” for Constructor) elementary requirements on connectivity of those networks which are reachable from some initial given network. We show some basic results on the (un-)decidability and hardness of dynamic model-checking problems.     

Erratum to “Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets”

This note corrects two errors that occurred during the typesetting of our paper “Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets”, which appeared in Hartmann et al. [Axiomatisations of functional dependencies in the presence of records, lists, sets and multisets, Theoret. Comput. Sci. 353(2) (2006) 167–196].     

Repetitiveness of languages generated by morphisms

We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive (Ehrenfeucht and Rozenberg, Inform. and Control 59 (1983) 13–35). From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of Séébold (Bull. EATCS 36 (1988) 137–151) on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(f) generated by f or the language SL(f) of subwords of L(f) are context-free or even regular.     

First-order spectra with one binary predicate

The spectrum, Sp(), of a sentence is the set of cardinalities of finite structures which satisfy . We prove that any set of integers which is in Func₁^∞, i.e. in the class of spectra of first-order sentences of type containing only unary function symbols, is also in BIN¹, i.e. in the class of spectra of first-order sentences of type involving only a single binary relation.

We give similar results for generalized spectra and some corollaries: in particular, from the fact that the large complexity class _cNTIME_RAM(cn) is included in Func₁^∞ for unary languages (n denotes the input integer), we deduce that the set of primes and many “natural” sets belong to BIN¹.

We also give some consequences for the image of spectra under polynomials of .     

Combined effects of in-plane boundary conditions and stiffening on buckling of eccentrically stringer-stiffened cylindrical panels

Donnel type stability equations for buckling of stringer stiffened cylindrical panels under combined axial compression and hydrostatic pressure are solved by the displacement approach of [6], The solution is employed for a parametric study over a wide range of panel and stringer geometries to evaluate the combined influence of panel configurations and boundary conditions along the straight edges on the buckling behavior of the panel relative to a complete “counter” cylinder (i.e. a cylinder with identical skin and stiffener parameters).

The parametric studies reveal a “sensitivity” to the “weak in shear”, N_x = N_xφ = 0, along the straight edges, SS1 boundary conditions type where the panel buckling loads are always smaller than those predicted for a complete “counter” cylinder. In the case of “classical”, SS3 B.Cs., there always exist values of panel width, 2φ₀, for which ρ = 1, i.e. the panel buckling load equals that of the complete “counter” cylinder. For SS2 and SS4 B.Cs. types, the nature by which the panel critical load approaches that of the complete cylinder appears to be panel configuration dependent.

Utilization of panels for the experimental determination of a complete cylinder buckling load is found to be satisfactory for relatively very lightly and heavily stiffened panels, as well as for short panels, (L/R) = 0.2 and 0.5. Panels of moderate length and stiffening have to be debarred, since they lead to nonconservative buckling load predictions.