Planar acyclic computation

This paper considers the following problem: given a specification consisting of a set of variables X, a multiset of functions F on those variables, and a cyclic ordering on X F, determine whether or not there exists a planar acyclic circuit which realizes the specification. An algorithm is given which produces such a circuit whenever one exists. In proving that our algorithm meets this requirement we provide some simple mathematical characterizations of those specifications which are realizable.     

Consistent Partial Matching of Shape Collections via Sparse Modeling

Recent efforts in the area of joint object matching approach the problem by taking as input a set of pairwise maps, which are then jointly optimized across the whole collection so that certain accuracy and consistency criteria are satisfied. One natural requirement is cycle‐consistency—namely the fact that map composition should give the same result regardless of the path taken in the shape collection. In this paper, we introduce a novel approach to obtain consistent matches without requiring initial pairwise solutions to be given as input. We do so by optimizing a joint measure of metric distortion directly over the space of cycle‐consistent maps; in order to allow for partially similar and extra‐class shapes, we formulate the problem as a series of quadratic programs with sparsity‐inducing constraints, making our technique a natural candidate for analysing collections with a large presence of outliers. The particular form of the problem allows us to leverage results and tools from the field of evolutionary game theory. This enables a highly efficient optimization procedure which assures accurate and provably consistent solutions in a matter of minutes in collections with hundreds of shapes.     

A Reprocessing Model for Complete Execution of RFID Access Operations on Tag Memory

This paper investigates the problem of inconsistent states of radio frequency identification (RFID) tag data caused by incomplete execution of read/write operations during access to RFID tag memory. Passive RFID tags require RF communication to access memory data. This study is motivated by the volatility of RF communication, where instability is caused by intermittent connections and uncertain communication. If a given tag disappears from the communication area of the reader during the reading or writing of tag data, the operation is incomplete, resulting in an inconsistent state of tag data. To avoid this inconsistency, it is necessary to ensure that any operations on tag memory are completed. In this paper, we propose an asynchronous reprocessing model for finalizing any incomplete execution of read/write operations to remove inconsistent states. The basic idea is to resume incomplete operations autonomously by detecting a tag’s reobservation from any reader. To achieve this, we present a concurrency control mechanism based on continuous query processing that enables the suspended tag operations to be re-executed. The performance study shows that our model improves the number of successful operations considerably in addition to suppressing inconsistent data access completely.     

A comparative study for consistency-based decision making with interval multiplicative preference relations

ABSTRACT

To ensure the reasonable application and perfect the theory of decision making with interval multiplicative preference relations (IMPRs), this paper continues to discuss decision making with IMPRs. After reviewing previous consistency concepts for IMPRs, we find that Krej?í’s consistency concept is more flexible and natural than others. However, it is insufficient to address IMPRs only using this concept. Considering this fact, this paper researches inconsistent and incomplete IMPRs that are usually encountered. First, programming models for addressing inconsistent and incomplete IMPRs are constructed. Then, this paper studies the consensus of individual IMPRs and defines a consensus index using the defined correlation coefficient. When the consensus requirement does not satisfy requirement, a programming model for improving consensus level is built, which can ensure the consistency. Subsequently, a procedure for group decision making with IMPRs is offered, and associated examples are provided to specifically show the application of main theoretical results.     

First-past-the-post games

Informally, a first-past-the-post game is a (probabilistic) game where the winner is the person who predicts the event that occurs first among a set of events. Examples of first-past-the-post games include so-called block and hidden patterns and the Penney-Ante game invented by Walter Penney. We formalise the abstract notion of a first-past-the-post game, and the process of extending a probability distribution on symbols of an alphabet to the plays of a game. We establish a number of properties of such games, for example, the property that an incomplete first-past-the-post game is also a first-past-the-post game.Penney-Ante games are multi-player games characterised by a collection of regular, prefix-free languages. Analysis of such games is facilitated by a collection of simultaneous (non-linear) equations in languages. Essentially, the equations are due to Guibas and Odlyzko. However, they did not formulate them as equations in languages but as equations in generating functions detailing lengths of words. For such games, we show how to use the equations in languages to calculate the probability of winning and how to calculate the expected length of a game for a given outcome. We also exploit the properties of first-past-the-post games to show how to calculate the probability of winning in the course of a play of the game. In this way, we avoid the construction of a deterministic finite-state machine or the use of generating functions, the two methods traditionally used for the task.We observe that Aho and Corasick's generalisation of the Knuth–Morris–Pratt pattern-matching algorithm can be used to construct the deterministic finite-state machine that recognises the language underlying a Penney-Ante game. The two methods of calculating the probabilities and expected values, one based on the finite-state machine and the other based on the non-linear equations in languages, have been implemented and verified to yield the same results.     

A relation-based method combining functional and structural testing for test case generation

Specification-based (or functional) testing enables us to detect errors in the implementation of functions defined in specifications, but since specifications are often incomplete in practice for some reasons (e.g., lack of ideas, no time to write), it is unlikely to be sufficient for testing all parts of corresponding programs. On the other hand, implementation-based (or structural) testing focuses on the examination of program structures, which allows us to test all parts of the programs, but may not be effective to show whether the programs properly implement the corresponding specifications. To perform a comprehensive testing of a program in practice, it is important to adopt both specification-based and implementation-based testing. In this paper we describe a relation-based test method that combines the specification-based and the implementation-based testing approaches. We establish a set of relations for test case generation, illustrate how the method is used with an example, and investigate the effectiveness and weakness of the method through an experiment on testing a software tool system.     

Multi-objective frequent termset clustering

Large media collections rapidly evolve in the World Wide Web. In addition to the targeted retrieval as is performed by search engines, browsing and explorative navigation is an important issue. Since the collections grow fast and authors most often do not annotate their web pages according to a given ontology, automatic structuring is in demand as a prerequisite for any pleasant human–computer interface. In this paper, we investigate the problem of finding alternative high-quality structures for navigation in a large collection of high-dimensional data. We express desired properties of frequent termset clustering (FTS) in terms of objective functions. In general, these functions are conflicting. This leads to the formulation of FTS clustering as a multi-objective optimization problem. The optimization is solved by a genetic algorithm. The result is a set of Pareto-optimal solutions. Users may choose their favorite type of a structure for their navigation through a collection or explore the different views given by the different optimal solutions. We explore the capability of the new approach to produce structures that are well suited for browsing on a social bookmarking data set.     

Complex neutrosophic set

Complex fuzzy sets and complex intuitionistic fuzzy sets cannot handle imprecise, indeterminate, inconsistent, and incomplete information of periodic nature. To overcome this difficulty, we introduce complex neutrosophic set. A complex neutrosophic set is a neutrosophic set whose complex-valued truth membership function, complex-valued indeterminacy membership function, and complex-valued falsehood membership functions are the combination of real-valued truth amplitude term in association with phase term, real-valued indeterminate amplitude term with phase term, and real-valued false amplitude term with phase term, respectively. Complex neutrosophic set is an extension of the neutrosophic set. Further set theoretic operations such as complement, union, intersection, complex neutrosophic product, Cartesian product, distance measure, and δ-equalities of complex neutrosophic sets are studied here. A possible application of complex neutrosophic set is presented in this paper. Drawbacks and failure of the current methods are shown, and we also give a comparison of complex neutrosophic set to all such methods in this paper. We also showed in this paper the dominancy of complex neutrosophic set to all current methods through the graph.

     

Algebraic methods for synthesizing majority gate networks

Summary The paper contains some new contributions to the problem of synthesizing an assigned function with three-input majority gates. The obtained networks have a tree structure and can be calculated using two different types of decompositions. The described procedures represent an improvement over the preceding solutions for the following reasons: 1) they are systematic and consist of simple algebraic operations; 2) they can be usefully employed for synthesizing incompletely specified functions; 3) the described methods lead in general to better solutions than those obtained with the other known procedures also in the syntesis of completely specified functions. This improvement derive from some new techniques consisting in introducing a set of incomplete specifications for taking in account the fact that more than one decomposition of a given function is possible.     

Automated Verification of Completeness and Consistency of Abstract State Machine Specifications using a SAT Solver

In the requirements engineering community, consistency and completeness have been identified as important properties of system specifications. Custom algorithms to verify these properties automatically have been devised for a number of specification languages, including SCR, RSML, and Statecharts. In this paper, we provide means to automatically verify completeness and consistency of Abstract State Machine (ASM) specifications. The verification is performed using a widely available tool, a SAT solver. The use of a SAT solver removes the need for designing and fine tuning language specific verification algorithms. Furthermore, the use of a SAT solver automates the verification procedure and produces a counterexample automatically when a specification is incomplete or inconsistent. We provide an algorithm to translate ASM specifications to a SAT problem instance. The translation is illustrated using the TASM toolset in conjunction with the “production cell system” case study.     

On the Reachability Problem for Uncertain Hybrid Systems

In this paper, we revisit the problem of designing controllers to meet safety specifications for hybrid systems, whose evolution is affected by both control and disturbance inputs. The problem is formulated as a dynamic game and an appropriate notion of hybrid strategy for the control inputs is developed. The design of hybrid strategies to meet safety specifications is based on an iteration of alternating discrete and continuous safety calculations. We show that, under certain assumptions, the iteration converges to a fixed point, which turns out to be the maximal set of states for which the safety specifications can be met. The continuous part of the calculation relies on the computation of the set of winning states for one player in a two player, two target, pursuit evasion differential game. We develop a characterization of these winning states (as well as the winning states for the other player for completeness) using methods from nonsmooth analysis and viability theory.     

Identification and robust control for systems with ellipsoidal parametric uncertainty by convex optimization

In this paper, sufficient conditions for robust output feedback controller design for systems with ellipsoidal parametric uncertainty are given in terms of solutions to a set of linear matrix inequalities (LMIs) Performance specifications are in terms of combined pole placement with sensitivity function shaping in the H₂ or H_∞ norm. Furthermore, an optimal input design technique for parameter estimation that is integrated into the robust control design is employed in this paper. This means that performance specifications on the closed‐loop transfer functions are translated into the requirements on the input signal spectrum. The simulation results show the effectiveness of the proposed method. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Monitoring Interfaces for Faults

We consider the problem of a module interacting with an external interface (environment) where the interaction is expected to satisfy some system specification Φ. While we have the full implementation details of the module, we are only given a partial external specification for the interface. The interface specification being partial (incomplete) means that the interface displays only a strict subset of the behaviors allowed by the interface specification.Based on the assumption that interface specifications are typically incomplete, we address the question of whether we can tighten the interface specification into a strategy, consistent with the given partial specification, that will guarantee that all possible interactions resulting from possible behaviors of the module will satisfy the system specification Φ. We refer to such a tighter specification as Φ-guaranteeing specification. Rather than verifying whether the interface, which is often an off-the-shelf component, satisfies the tighter specification, the paper proposes a construction of a run-time monitor which continuously checks the existence of a Φ-guaranteeing interface.We view the module and the external interface as players in a 2-player game. The interface has a winning strategy if it can guarantee that no matter what the module does, the overall specification Φ is met. The problem of incomplete specifications is resolved by allowing the interface to follow any strategy consistent with the interface specification. Our approach essentially combines traditional run-time monitoring and static analysis. This allows going beyond the focus of traditional run-time monitoring tools – error detection in the execution trace, towards the focus of the static analysis – bug detection in the programs.     

Approximation reduction in inconsistent incomplete decision tables

This article deals with approaches to attribute reductions in inconsistent incomplete decision table. The main objective of this study is to extend a kind of attribute reductions called a lower approximation reduct and an upper approximation reduct, which preserve the lower/upper approximation distribution of a target decision. Several judgement theorems of a lower/upper approximation consistent set in inconsistent incomplete decision table are educed. Then, the discernibility matrices associated with the two approximation reductions are examined as well, from which we can obtain approaches to attribute reduction of an incomplete decision table in rough set theory.     

Behavioral specification of reactive systems using stream-based I/O tables

A core problem in formal methods is the transition from informal requirements to formal specifications. Especially when specifying the behavior of reactive systems, many formalisms require the user to either understand a complex mathematical theory and notation or to derive details not given in the requirements, such as the state space of the problem. For many approaches also a consistent set of requirements is needed, which enforces to resolve requirements conflicts prior to formalization. This paper describes a specification technique, where not states but signal patterns are the main elements. The notation is based on tables of regular expressions and supports a piece-wise formalization of potentially inconsistent requirements. Many properties, such as input completeness and consistency, can be checked automatically for these specifications. The detection and resolution of conflicts can be performed within our framework after formalization. Besides the formal foundation of our approach, this paper presents prototypical tool support and results from an industrial case study.     

Agents that argue and explain classifications

Argumentation is a promising approach used by autonomous agents for reasoning about inconsistent/incomplete/uncertain knowledge, based on the construction and the comparison of arguments. In this paper, we apply this approach to the classification problem, whose purpose is to construct from a set of training examples a model that assigns a class to any new example. We propose a formal argumentation-based model that constructs arguments in favor of each possible classification of an example, evaluates them, and determines among the conflicting arguments the acceptable ones. Finally, a “valid” classification of the example is suggested. Thus, not only the class of the example is given, but also the reasons behind that classification are provided to the user as well in a form that is easy to grasp. We show that such an argumentation-based approach for classification offers other advantages, like for instance classifying examples even when the set of training examples is inconsistent, and considering more general preference relations between hypotheses. In the particular case of concept learning, the results of version space theory developed by Mitchell are retrieved in an elegant way in our argumentation framework. Finally, we show that the model satisfies the rationality postulates identified in argumentation literature. This ensures that the model delivers sound results. This article extends and revises results presented in preliminary form in the paper [9].     

Incomplete oblique projections method for solving regularized least-squares problems in image reconstruction

In this paper we improve on the incomplete oblique projections (IOP) method introduced previously by the authors for solving inconsistent linear systems, when applied to image reconstruction problems. That method uses IOP onto the set of solutions of the augmented system Ax?r=b, and converges to a weighted least‐squares solution of the system Ax=b. In image reconstruction problems, systems are usually inconsistent and very often rank‐deficient because of the underlying discretized model. Here we have considered a regularized least‐squares objective function that can be used in many ways such as incorporating blobs or nearest‐neighbor interactions among adjacent pixels, aiming at smoothing the image. Thus, the oblique incomplete projections algorithm has been modified for solving this regularized model. The theoretical properties of the new algorithm are analyzed and numerical experiments are presented showing that the new approach improves the quality of the reconstructed images.     

Latticed-LTL synthesis in the presence of noisy inputs

In the classical synthesis problem, we are given a specification ψ over sets of input and output signals, and we synthesize a finite-state transducer that realizes ψ: with every sequence of input signals, the transducer associates a sequence of output signals so that the generated computation satisfies ψ. In recent years, researchers consider extensions of the classical Boolean setting to a multi-valued one. We study a multi-valued setting in which the truth values of the input and output signals are taken from a finite lattice, and so is the satisfaction value of specifications. We consider specifications in latticed linear temporal logic (LLTL). In LLTL, conjunctions and disjunctions correspond to the meet and join operators of the lattice, respectively, and the satisfaction values of formulas are taken from the lattice too. The lattice setting arises in practice, for example in specifications involving priorities or in systems with inconsistent viewpoints. We solve the LLTL synthesis problem, where the goal is to synthesize a transducer that realizes the given specification in a desired satisfaction value. For the classical synthesis problem, researchers have studied a setting with incomplete information, where the truth values of some of the input signals are hidden and the transducer should nevertheless realize ψ. For the multi-valued setting, we introduce and study a new type of incomplete information, where the truth values of some of the input signals may be noisy, and the transducer should still realize ψ in the desired satisfaction value. We study the problem of noisy LLTL synthesis, as well as the theoretical aspects of the setting, like the amount of noise a transducer may tolerate, or the effect of perturbing input signals on the satisfaction value of a specification. We prove that the noisy-synthesis problem for LLTL is 2EXPTIME-complete, as is traditional LTL synthesis.     

A general framework for computing maximal contractions

This paper investigates the problem of computing all maximal contractions of a given formula set Γ with respect to a consistent set Δ of atomic formulas and negations of atomic formulas. We first give a constructive definition of minimal inconsistent subsets and propose an algorithmic framework for computing all minimal inconsistent subsets of any given formula set. Then we present an algorithm to compute all maximal contractions fromminimal inconsistent subsets. Based on the algorithmic framework and the algorithm, we propose a general framework for computing all maximal contractions. The computability of the minimal inconsistent subset and maximal contraction problems are discussed. Finally, we demonstrate the ability of this framework by applying it to the first-order language without variables and design an algorithmfor the computation of all maximal contractions.