Comments on “Combinatorial rule explosion eliminated by afuzzy rule configuration” [and reply]

In the original paper (IEEE Trans. Fuzzy Syst., vol.6, p.1-11, 1998), Combs and Andrews proved the following logical equivalence (stated here for two antecedents p and q and one consequent r, but easily generalize to an arbitrary number of antecedents and consequents): [(p∧q)⇒r]⇔[(p⇒r)V(q⇒r)]. This is a very significant result because it suggests that we can replace multi-antecedent rules with an interconnection of single antecedent rules, which eliminates the rule explosion that is associated with multi-antecedent rules. Combs and Andrews refer to the left-hand side of this equivalence as an intersection rule configuration (IRC) and to its right-hand side as a union rule configuration (URC). Their result gives rise to two distinctly different paths for the design of fuzzy logic systems; IRC, which leads to rule explosion, and URC, which does not. The authors discuss four points about the IRC⇔URC relation. The original authors reply, acknowledging some of the points and stating that they would present their results differently if starting now     

弱可逆拟(r,r)阶存贮线性有限自动机的分解

通过对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机输出权的研究,得出对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机的任意一个状态,它的长r的输出权都是1;任何一个n元拟(r,r)阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件是M都可以分解为一个延迟0步弱可逆有限自动机M0和一个延迟r步弱可逆拟(0,r)阶存贮线性有限自动机M1。     

Theory Extension in ACL2(r)

ACL2(r) is a modified version of the theorem prover ACL2 that adds support for the irrational numbers using nonstandard analysis. It has been used to prove basic theorems of analysis, as well as the correctness of the implementation of transcendental functions in hardware. This paper presents the logical foundations of ACL2(r). These foundations are also used to justify significant enhancements to ACL2(r).      

Distributed On-the-Fly Equivalence Checking

On-the-fly equivalence checking consists in comparing two Labeled Transition Systems (Ltss) modulo a given equivalence relation by exploring them in a demand-driven way. Since it avoids the explicit construction of Ltss, this method is able to detect errors even in systems that are too large to fit in the memory of a computer. In this paper, we aim at further improving the performance of on-the-fly equivalence checking using several machines connected by a network. We propose DSolve, a new algorithm for distributed on-the-fly resolution of Boolean Equation Systems (Bess), which enables equivalence checking modulo various relations characterized in terms of Bess. DSolve serves as verification engine for the distributed version of Bisimulator, an on-the-fly equivalence checker developed within the Cadp verification toolbox using the Open/Cæsar environment. Our experimental measures show quasi-linear speedups and a good scalability of the distributed version of Bisimulator w.r.t. its sequential version.     

On nonlinear H∞ control under sampled measurements

This paper deals with the nonlinear H_∞ control problem with sampled measurement feedback. This problem has already been studied in Suzuki et al. (1995), where, using a certainty equivalence principle, a control solution involving a state estimator with a linear injection gain is proposed. Using the same general framework, we propose a more refined estimator with a nonlinear injection gain. This gain is shown to be connected to a periodic solution of a Hamilton-Jacobi inequality with jumps     

UNCERTAINTY AND COMPLEMENTARITY PRINCIPLES IN ECOLOGICAL MODELS

Literature about models and modelling is very extensive, but the linguistic aspect of ecological models is not so popular. In this paper, the authors develop a linguistic theory of ecological models from the mathematical linguistic theory and its semantic background. From the equivalence relationship defined upon the language L(M), which describes an ecological model in mathematical terms, it will be possible to statistically determine the semantic component associated to each sentence. The authors also propose an uncertainty principle for the equations (called flow equations) that are used to model ecological processes. The following hypothesis will be considered: a) The first-order vocabulary associated to a variable, a transformed function, is a sememe; b) The flow equation is a complex sentence; c) There is a synonymy relationship among sentences that describe the same process; d) The synonymy relationship forms classes of equivalence. The following results will be reported: a) The cardinal of each class of equivalence is a dimension of the process complexity; b) Each sentence can be defined through a pair of numbers (r,m)ER, 0 < =r < =1, 0 < =m < =1, where r defines the coefficient of determination and m the emotional component of meaning (semantics) of the equation; c) The meaning m can be calculated approximately by statistical methods; d) An uncertainty principle (Delta r . Delta m < =0) and a semantic complementarity principle are proposed.     

Efficient Methods for kr → r and r → kr Array Redistribution1

Array redistribution is usually required to enhance algorithm performance in many parallel programs on distributed memory multicomputers. Since it is performed at run-time, there is a performance tradeoff between the efficiency of new data decomposition for a subsequent phase of an algorithm and the cost of redistributing data among processors. In this paper, we present efficient algorithms for BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) and BLOCK-CYCLIC(r) to BLOCK-CYCLIC(kr) redistribution. The most significant improvement of our methods is that a processor does not need to construct the send/receive data sets for a redistribution. Based on the packing/unpacking information that derived from the BLOCK-CYCLIC(kr) to BLOCK-CYCLIC(r) redistribution and vice versa, a processor can pack/unpack array elements into (from) messages directly. To evaluate the performance of our methods, we have implemented our methods along with the Thakur's methods and the PITFALLS method on an IBM SP2 parallel machine. The experimental results show that our algorithms outperform the Thakur's methods and the PITFALLS method for all test samples. This result encourages us to use the proposed algorithms for array redistribution.     

Deterministic asynchronous automata for infinite traces

This paper shows the equivalence between the family of recognizable languages over infinite traces and the family of languages which are recognized by deterministic asynchronous cellular Muller automata. We thus give a proper generalization of McNaughton's Theorem from infinite words to infinite traces. Thereby we solve one of the main open problems in this field. As a special case we obtain that every closed (w.r.t. the independence relation) word language is accepted by someI-diamond deterministic Muller automaton.This research has been supported by the ESPRIT Basic Research Action No. 6317 ASMICS 2.     

Comments on ‘Admissibility and static output‐feedback stabilization of singular Markovian jump systems with defective statistics of modes transitions’

This document shows that the proof of Theorem 3.3 in the work of Liu et al (Int J Robust Nonlinear Control. 2015. 10.1002/rnc.3108) is incorrect and, thus, the theorem is not proved. Since the results of the paper are strongly based on this theorem, the problem has to be addressed. If a natural correction is introduced, the problem still holds. Therefore, a new linear matrix inequality is proposed here to show its equivalence with the stochastic stability of a Markov jump linear singular system under a similar assumption as that in the work of Liu et al.     

Some algebraic laws for spans (and their connections with multirelations)

This paper investigates some key algebraic properties of the categories of spans and cospans (up to isomorphic supports) over the category Set of (small) sets and functions, analyzing the monoidal structures induced over both spans and cospans by cartesian product and disjoint union of sets. Our results find analogous counterparts in (and are partly inspired by) the theory of relational algebras, thus our paper also sheds some light on the relationship between (co)spans and the categories of (multi)relations and of equivalence relations. And, since (co)spans yield an intuitive presentation of dynamical systems with input and output interfaces, our results introduce an expressive, two-fold algebra that can serve as a specification formalism for rewriting systems and for composing software modules.     

Élie Cartan’s geometrical vision or how to avoid expression swell

The aim of the paper is to demonstrate the superiority of Cartan’s method over direct methods based on differential elimination for handling otherwise intractable equivalence problems. In this sense, using our implementation of Cartan’s method, we establish two new equivalence results. We establish when a system of second order ODEs is equivalent to flat system (second derivations are zero), and when a system of holomorphic PDEs with two independent variables and one dependent variable is flat. We consider the problem of finding transformation that brings a given equation to the target one. We shall see that this problem becomes algebraic when the symmetry pseudogroup of the target equation is zerodimensional. We avoid the swelling of the expressions, by using non-commutative derivations adapted to the problem.     

Equivalence of rational representations of behaviors

This article deals with the equivalence of representations of behaviors of linear differential systems. In general, the behavior of a given linear differential system has many different representations. In this paper we restrict ourselves to kernel and image representations. Two kernel representations are called equivalent if they represent one and the same behavior. For kernel representations defined by polynomial matrices, necessary and sufficient conditions for equivalence are well known. In this paper, we deal with the equivalence of rational representations, i. e. kernel and image representations that are defined in terms of rational matrices. As the first main result of this paper, we will derive a new condition for the equivalence of rational kernel representations of possibly noncontrollable behaviors. Secondly we will derive conditions for the equivalence of rational representations of a given behavior in terms of the polynomial modules generated by the rows of the rational matrices. We will also establish conditions for the equivalence of rational image representations. Finally, we will derive conditions under which a given rational kernel representation is equivalent to a given rational image representation.     

Infinitary rewriting: closure operators, equivalences and models

Infinitary Term Rewriting allows to express infinite terms and transfinite reductions that converge to those terms. Underpinning the machinery of infinitary rewriting are closure operators on relations that facilitate the formation of transfinite reductions and transfinite equivalence proofs. The literature on infinitary rewriting has largely neglected to single out such closure operators, leaving them implicit in definitions of (transfinite) rewrite reductions, or equivalence relations. This paper unpicks some of those definitions, extracting the underlying closure principles used, as well as constructing alternative operators that lead to alternative notions of reduction and equivalence. A consequence of this unpicking is an insight into the abstraction level at which these operators can be defined. Some of the material in this paper already appeared in Kahrs (2010). The paper also generalises the notion of equational model for infinitary rewriting. This leads to semantics-based notions of equivalence that tie in with the equivalences constructed from the closure operators.     

How Many Queries Are Needed to Learn One Bit of Information?

In this paper we study the question how many queries are needed to halve a given version space. In other words: how many queries are needed to extract from the learning environment the one bit of information that rules out fifty percent of the concepts which are still candidates for the unknown target concept. We relate this problem to the classical exact learning problem. For instance, we show that lower bounds on the number of queries needed to halve a version space also apply to randomized learners (whereas the classical adversary arguments do not readily apply). Furthermore, we introduce two new combinatorial parameters, the halving dimension and the strong halving dimension, which determine the halving complexity (modulo a small constant factor) for two popular models of query learning: learning by a minimum adequate teacher (equivalence queries combined with membership queries) and learning by counterexamples (equivalence queries alone). These parameters are finally used to characterize the additional power provided by membership queries (compared to the power of equivalence queries alone). All investigations are purely information-theoretic and ignore computational issues.     

Trace Machines for Observing Continuous-Time Markov Chains

In this paper, we study several linear-time equivalences (Markovian trace equivalence, failure and ready trace equivalence) for continuous-time Markov chains that refer to the probabilities for timed execution paths. Our focus is on testing scenarios by means of push-button experiments with appropriate trace machines and a discussion of the connections between the equivalences. For Markovian trace equivalence, we provide alternative characterizations, including one that abstracts away from the time instances where actions are observed, but just reports on the average sojourn times in the states. This result is used for a reduction of the question whether two finite-state continuous-time Markov chains are Markovian trace equivalent to the probabilistic trace equivalence problem for discrete-time Markov chains (and the latter is known to be solvable in polynomial time).     

A fully abstract semantics for causality in the \pi-calculus

We examine the meaning of causality in calculi for mobile processes like the -calculus, and we investigate the relationship between interleaving and causal semantics for such calculi. We separate two forms of causal dependencies on actions of -calculus processes, called subject and object dependencies: The former originate from the nesting of prefixes and are propagated through interactions among processes (they are the only form of causal dependencies present in CCS-like languages); the latter originate from the binding mechanisms on names. We propose a notion of causal bisimulation which distinguishes processes which differ for the subject or for the object dependencies. We show that this causal equivalence can be reconducted to, or implemented into, the ordinary interleaving observation equivalence. We prove that our encoding is fully abstract w.r.t. the two behavioural equivalences. This allows us to exploit the simpler theory of the interleaving semantics to reason about the causal one. In [San94b] a similar programme is carried out for location bisimulation [BCHK91], a non-interleaving spatial-sensitive (as opposed to causal-sensitive) behavioural equivalence. The comparison between the encodings of causal bisimulation in this paper, and of location bisimulation in [San94b], evidences the similarities and the differences between these two equivalences. Received 11 December 1995 / 16 June 1997     

Immersion‐ and invariance‐based adaptive stabilization of switched nonlinear systems

This paper presents a novel framework to asymptotically adaptively stabilize a class of switched nonlinear systems with constant linearly parameterized uncertainty. By exploiting the generalized multiple Lyapunov functions method and the recently developed immersion and invariance (I&I) technique, which does not invoke certainty equivalence, we design the error estimator, continuous state feedback controllers for subsystems, and a switching law to ensure boundedness of all closed‐loop signals and global asymptotical regulation of the states, where the solvability of the I&I adaptive stabilization problem for individual subsystems is not required. Then, along with the backstepping method, the proposed design technique is further applied to a class of switched nonlinear systems in strict‐feedback form with an unknown constant parameter so that the I&I adaptive stabilization controllers for the system is developed. Finally, simulation results are also provided to demonstrate the effectiveness of the proposed design method.     

Extensions of fuzzy hyperideals in <Emphasis Type="Italic">H</Emphasis><Subscript><Emphasis Type="Italic">V</Emphasis></Subscript>-semigroups

The object of the present paper is the investigation and study of (fuzzy) hyperideals in H _v - semigroups. Regular equivalence relations play in H _v - semigroup theory a role analogous to congruences in semigroup theory, so we introduce fuzzy regular equivalence relations on H _v -semigroups and then we study fuzzy Rees regular relations on H _v -semigroups. Using this ideas, we establish a relation between fuzzy hyperideal of an H _v -semigroup H and fuzzy hyperideal of a quotient H _v -semigroup of H. Some characterizations of them are then shown.      

Equivalence of queries that are sensitive to multiplicities

The query equivalence problem has been studied extensively for set-semantics and, more recently, for bag and bag-set semantics. However, SQL queries often combine set, bag and bag-set semantics. For example, an SQL query that returns a multiset of elements may call a subquery or view that returns a set of elements. Queries may access both relations that do not contain duplicates, as well as relations with duplicates. As another example, in SQL one can compute a multiset-union of queries, each of which returns a set of answers. This paper presents combined semantics, which formally models query evaluation combining set, bag and bag-set semantics. The equivalence problem for queries evaluated under combined semantics is studied. A sufficient condition for equivalence is presented. For several important common classes of queries necessary and sufficient conditions for equivalence are presented. An early version of this article appeared in [7]. This paper extends [7] to include bag semantics, in addition to set and bag-set semantics. This work was partially supported by the Israel Science Foundation (Grant 1032/05).     

Simulation Preorder over Simple Process Algebras

We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows us to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems. In particular, we show that simulation preorder (in both directions) and simulation equivalence are decidable in EXPTIME between pushdown processes and finite-state ones. On the other hand, simulation preorder is undecidable between PA and finite-state processes in both directions. These results also hold for those PA and finite-state processes which are deterministic and normed, and thus immediately extend to trace preorder. Regularity (finiteness) w.r.t. simulation and trace equivalence is also shown to be undecidable for PA. Finally, we prove that simulation preorder (in both directions) and simulation equivalence are intractable between all classes of infinite-state systems (in the hierarchy of process rewrite systems) and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard and the other direction is co -hard; consequently, simulation equivalence between BPA (or BPP) and finite-state processes is also co -hard.