Relative coobservability for decentralised supervisory control of discrete-event systems

In this paper, we study the concept of relative coobservability in decentralised supervisory control of discrete-event systems under partial observation. This extends our previous work on relative observability from a centralised setup to a decentralised one. A fundamental concept in decentralised supervisory control is coobservability (and its several variations); this property is not, however, closed under set union, and hence there generally does not exist the supremal element. Our proposed relative coobservability, although stronger than coobservability, is algebraically well behaved, and the supremal relatively coobservable sublanguage of a given language exists. We present a language-based algorithm to compute this supremal sublanguage; the algorithm allows straightforward implementation using off-the-shelf algorithms. Moreover, relative coobservability is weaker than conormality, which is also closed under set union; unlike conormality, relative coobservability imposes no constraint on disabling unobservable controllable events.     

A necessary and sufficient condition for diagnosability of stochastic discrete event systems

Stochastic discrete event systems (SDES) are systems whose evolution is described by the occurrence of a sequence of events, where each event has a defined probability of occurring from each state. The diagnosability problem for SDES is the problem of determining the conditions under which occurrences of a fault can be detected in finite time with arbitrarily high probability. (IEEE Trans Autom Control 50(4):476–492 2005) proposed a class of SDES and proposed two definitions of stochastic diagnosability for SDES called A- and A A-diagnosability and reported a necessary and sufficient condition for A-diagnosability, but only a sufficient condition for A A-diagnosability. In this paper, we provide a condition that is both necessary and sufficient for determining whether or not an SDES is A A-diagnosable. We also show that verification of A A-diagnosability is equivalent to verification of the termination of the cumulative sum (CUSUM) procedure for hidden Markov models, and that, for a specific class of SDES called fault-immediate systems, the sequential probability ratio test (SPRT) minimizes the expected number of observable events required to distinguish between the normal and faulty modes.     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

A temporal modal defeasible logic for formalizing social commitments in dialogue and argumentation models

In this paper, we extend a temporal defeasible logic with a modal operator Committed to formalize commitments that agents undertake as a consequence of communicative actions (speech acts) during dialogues. We represent commitments as modal sentences. The defeasible dual of the modal operator Committed is a modal operator called Exempted. The logical setting makes the social-commitment based semantics of speech acts verifiable and practical; it is possible to detect if, and when, a commitment is violated and/or complied with. One of the main advantages of the proposed system is that it allows for capturing the nonmonotonic behavior of the commitments induced by the relevant speech acts.     

A formal algorithmic language FALGOL. Thirty years after

FALGOL (Formal ALGOrithmic Language) is a fundamental theoretical model of high-level operational languages with unrestricted program object hierarchy. This model formalizes binding, assignment, substitution, and recursion; moreover, the principle of dynamic binding is implemented in the model in contrast to other formal systems of this sort, which makes FALGOL appropriate to specify the most difficultly formalized concepts in modern object programming languages.     

Decidability and closure properties of weak Petri net languages insupervisory control

We extend the class of control problems that can be modeled by Petri nets considering the notion of weak terminal behavior. Deterministic weak languages represent closed-loop terminal behaviors that may be enforced by nonblocking Petri net supervisors if controllable. The class of deterministic weak PN languages is not closed under the supremal controllable sublanguage operator     

Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata

For each sufficiently large n, there exists a unary regular language L such that both L and its complement L ^c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least \(e^{\Omega(\sqrt[3]{n\cdot\ln^{2}n})}\). Actually, L and L ^c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.     

On error-free filtering of finite-state singular processes under dependent distortions

We consider the problem of finding some sufficient conditions under which causal error-free filtering for a singular stationary stochastic process X = {X _n} with a finite number of states from noisy observations is possible. For a rather general model of observations where the observable stationary process is absolutely regular with respect to the estimated process X, it is proved (using an information-theoretic approach) that under a natural additional condition, the causal error-free (with probability one) filtering is possible.     

What Makes an Effective Representation of Information: A Formal Account of Observational Advantages

In order to effectively communicate information, the choice of representation is important. Ideally, a chosen representation will aid readers in making desired inferences. In this paper, we develop the theory of observation: what it means for one statement to be observable from another. Using observability, we give a formal characterization of the observational advantages of one representation of information over another. By considering observational advantages, people will be able to make better informed choices of representations of information. To demonstrate the benefit of observation and observational advantages, we apply these concepts to set theory and Euler diagrams. In particular, we can show that Euler diagrams have significant observational advantages over set theory. This formally justifies Larkin and Simon’s claim that “a diagram is (sometimes) worth ten thousand words”.     

The Sum 2KM(x)−K(x) Over All Prefixes x of Some Binary Sequence Can be Infinite

We consider two quantities that measure complexity of binary strings: KM(x) is defined as the negative logarithm of continuous a priori probability on the binary tree, and K(x) denotes prefix complexity of a binary string x. In this paper we answer a question posed by Joseph Miller and prove that there exists an infinite binary sequence ω such that the sum of 2^KM(x)?K(x) over all prefixes x of ω is infinite. Such a sequence can be chosen among characteristic sequences of computably enumerable sets.     

Occurrence indices of elements in linear recurrence sequences over primary residue rings

We study distances to the first occurrence (occurrence indices) of a given element in a linear recurrence sequence over a primary residue ring \(\mathbb{Z}_{p^n } \). We give conditions on the characteristic polynomial F(x) of a linear recurrence sequence u which guarantee that all elements of the ring occur in u. For the case where F(x) is a reversible Galois polynomial over \(\mathbb{Z}_{p^n } \), we give upper bounds for occurrence indices of elements in a linear recurrence sequence u. A situation where the characteristic polynomial F(x) of a linear recurrence sequence u is a trinomial of a special form over ?₄ is considered separately. In this case we give tight upper bounds for occurrence indices of elements of u.     

A new strategy for generating shortest addition sequences

An addition sequence problem is given a set of numbers X = {n ₁, n ₂, . . . , n _m }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n _j , 1 ≤ j ≤ m, in the search tree.     

Novel steganographic method based on generalized <Emphasis Type="Italic">K</Emphasis>-distance <Emphasis Type="Italic">N</Emphasis>-dimensional pixel matching

In this paper, a steganographic scheme adopting the concept of the generalized K _d -distance N-dimensional pixel matching is proposed. The generalized pixel matching embeds a B-ary digit (B is a function of K and N) into a cover vector of length N, where the order-d Minkowski distance-measured embedding distortion is no larger than K. In contrast to other pixel matching-based schemes, a N-dimensional reference table is used. By choosing d, K, and N adaptively, an embedding strategy which is suitable for arbitrary relative capacity can be developed. Additionally, an optimization algorithm, namely successive iteration algorithm (SIA), is proposed to optimize the codeword assignment in the reference table. Benefited from the high dimensional embedding and the optimization algorithm, nearly maximal embedding efficiency is achieved. Compared with other content-free steganographic schemes, the proposed scheme provides better image quality and statistical security. Moreover, the proposed scheme performs comparable to state-of-the-art content-based approaches after combining with image models.     

Chain sequences with ordered enclosing

To enhance the efficiency of numerical control machines for cutting of sheet material, a method of searching for the cutter trajectory as a path with ordered enclosing in the flat graph G = (V, E) corresponding to the cutting design is proposed. It is shown that this path can be represented as a sequence of no more than n/2 + 1 chains with ordered enclosing, where n is the number of odd-order vertices in G. An algorithm for finding the sought sequence of chains, with a complexity of O(|E|) is developed.     

(<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-Distance Antimagic Labeling of Some Types of Graphs

We analyze the necessary existence conditions for (a, d)-distance antimagic labeling of a graph G = (V, E) of order n. We obtain theorems that expand the family of not (a, d) -distance antimagic graphs. In particular, we prove that the crown P _n ○ P ₁ does not admit an (a, 1)-distance antimagic labeling for n ≥ 2 if a ≥ 2. We determine the values of a at which path P _n can be an (a, 1)-distance antimagic graph. Among regular graphs, we investigate the case of a circulant graph.     

A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator

In this paper, we propose a new primal–dual algorithm for minimizing \(f({\mathbf {x}})+g({\mathbf {x}})+h({\mathbf {A}}{\mathbf {x}})\), where f, g, and h are proper lower semi-continuous convex functions, f is differentiable with a Lipschitz continuous gradient, and \({\mathbf {A}}\) is a bounded linear operator. The proposed algorithm has some famous primal–dual algorithms for minimizing the sum of two functions as special cases. E.g., it reduces to the Chambolle–Pock algorithm when \(f=0\) and the proximal alternating predictor–corrector when \(g=0\). For the general convex case, we prove the convergence of this new algorithm in terms of the distance to a fixed point by showing that the iteration is a nonexpansive operator. In addition, we prove the O(1 / k) ergodic convergence rate in the primal–dual gap. With additional assumptions, we derive the linear convergence rate in terms of the distance to the fixed point. Comparing to other primal–dual algorithms for solving the same problem, this algorithm extends the range of acceptable parameters to ensure its convergence and has a smaller per-iteration cost. The numerical experiments show the efficiency of this algorithm.     

Observability and decentralized control of fuzzy discrete-event systems

Fuzzy discrete-event systems as a generalization of (crisp) discrete-event systems have been introduced in order that it is possible to effectively represent uncertainty, imprecision, and vagueness arising from the dynamic of systems. A fuzzy discrete-event system has been modeled by a fuzzy automaton; its behavior is described in terms of the fuzzy language generated by the automaton. In this paper, we are concerned with the supervisory control problem for fuzzy discrete-event systems with partial observation. Observability, normality, and co-observability of crisp languages are extended to fuzzy languages. It is shown that the observability, together with controllability, of the desired fuzzy language is a necessary and sufficient condition for the existence of a partially observable fuzzy supervisor. When a decentralized solution is desired, it is proved that there exist local fuzzy supervisors if and only if the fuzzy language to be synthesized is controllable and co-observable. Moreover, the infimal controllable and observable fuzzy superlanguage, and the supremal controllable and normal fuzzy sublanguage are also discussed. Simple examples are provided to illustrate the theoretical development.     

Efficient and secure multi secret sharing schemes based on boolean XOR and arithmetic modulo

Multi Secret Sharing (MSS) scheme is an efficient method of transmitting more than one secret securely. In (n, n)-MSS scheme n secrets are used to create n shares and for reconstruction, all n shares are required. In state of the art schemes n secrets are used to construct n or n + 1 shares, but one can recover partial secret information from less than n shares. There is a need to develop an efficient and secure (n, n)-MSS scheme so that the threshold property can be satisfied. In this paper, we propose three different (n, n)-MSS schemes. In the first and second schemes, Boolean XOR is used and in the third scheme, we used Modular Arithmetic. For quantitative analysis, Similarity metrics, Structural, and Differential measures are considered. A proposed scheme using Modular Arithmetic performs better compared to Boolean XOR. The proposed (n, n)-MSS schemes outperform the existing techniques in terms of security, time complexity, and randomness of shares.     

Mixed <Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>/<Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> control for linear infinite-dimensional systems

In this paper, we consider mixed H ₂/H _∞ control problems for linear infinite-dimensional systems. The first part considers the state feedback control for the H ₂/H _∞ control problems of linear infinite-dimensional systems. The cost horizon can be infinite or finite time. The solutions of the H ₂/H _∞ control problem for linear infinitedimensional systems are presented in terms of the solutions of the coupled operator Riccati equations and coupled differential operator Riccati equations. The second part addresses the observer-based H ₂/H _∞ control of linear infinite-dimensional systems with infinite horizon and finite horizon costs. The solutions for the observer-based H ₂/H _∞ control problem of linear infinite-dimensional systems are represented in terms of the solutions of coupled operator Riccati equations. The first-order partial differential system examples are presented for illustration. In particular, for these examples, the Riccati equations are represented in terms of the coefficients of first-order partial differential systems.     

Upper bound on the minimum distance of LDPC codes over <Emphasis Type="Italic">GF</Emphasis>(<Emphasis Type="Italic">q</Emphasis>) based on counting the number of syndromes

In [1] a syndrome counting based upper bound on the minimum distance of regular binary LDPC codes is given. In this paper we extend the bound to the case of irregular and generalized LDPC codes over GF(q). A comparison with the lower bound for LDPC codes over GF(q), upper bound for the codes over GF(q), and the shortening upper bound for LDPC codes is made. The new bound is shown to lie under the Gilbert–Varshamov bound at high rates.