Search

Highlights • And-cross transitions are a useful abstraction that can make some constructs easier to specify for the modeler. • They can be transformed to and from alternative modeling solutions that require a greater number of transitions. • With fewer transitions, the time taken and memory required to certify a model to be deterministic using formal methods can be much reduced compared to other approaches. This is related to the time and memory required to compute the set of pairs of potentially conflicting transitions. Abstract In this paper, we present an approach to formally encode state machines expressed in Umple for symbolic verification. We illustrate this with a real-world modeling example that encodes and analyzes and-cross transitions. This paper discusses a formal description of our approach to represent state machine systems under analysis (SSUAs); a systematic approach to certifying that SSUAs are deterministic; and an evaluation of performance (memory usage and execution time) on the case study. Method We describe a formalization of state machines in Umple that enables their translation to model checking tools and also to code that is consistent with this. We present three alternative modeling solutions for a sample problem and a solution based on the use of and-cross transitions. State machine models corresponding to these solutions are represented in Umple, a model-oriented programming language. These are automatically transformed to SMV, the input language of the nuXmv (or NuSMV) model checker. By cleanly separating concerns, we systematically integrate components of hierarchical state systems as opposed to the traditional flattening approach, yet manage the complexity introduced by concurrency and and-crossing. We then compose and verify a set of requirements (e.g., correctness, safety, liveliness, etc.) on the resulting systems of all the modeling approaches to empirically compare the different modeling alternatives with the use of and-cross transitions. Results We can encode and formally analyse complex state machines with and-cross transition(s). We observed a large reduction in the number of required transitions for encoding the SSUA, as opposed to the alternative approaches. We asserted that solutions derived from the approaches are identical behavior-wise even though each approach models the SSUA differently. Each of the approaches yielded the same result for potentially conflicting pairs which is a false positive (i.e., the SSUAs are deterministic). We observe that each approach maintains the same global state-space irrespective of the variations in their number of transitions. Furthermore, we observe that it is untrue that a more abstract method applied to an SSUA outperforms its less abstract counterpart whenever parameters (such as execution time, memory usage and the number of Binary Decision Diagrams - BDDs) are the factors under consideration. Contributions A systematic approach to encode state machines with and-cross transitions (including unusual transitions). An enhanced but fully automated approach to discovering nondeterminism in state machines even in the presence of unbounded domains and multiple and-cross transitions within the same enclosing orthogonal state. An empirical study of the impact of abstraction on some performance parameters. We also present an extended formalization of Umple state machines. [ABSTRACT FROM AUTHOR]

Abstract: The study of the behaviour of non-deterministic automata has traditionally focused on the languages which can be associated to the different states. Under this interpretation, the different branches that can be taken at every step are ignored. However, we can also take into account the different decisions which can be made at every state, that is, the branches that can be taken, and these decisions might change the possible future behaviour. In this case, the behaviour of the automata can be described with the help of the concept of bisimilarity. This is the kind of description that is usually obtained when the automata are regarded as labelled transition systems or coalgebras. Contrarily to what happens with deterministic automata, it is not possible to describe the behaviour up to bisimilarity of states of a non-deterministic automaton by considering just the languages associated to them. In this paper we present a description of a final object for the category of non-deterministic automata, regarded as labelled transition systems, with the help of some structures defined in terms of languages. As a consequence, we obtain a characterisation of bisimilarity of states of automata in terms of languages and a method to minimise non-deterministic automata with respect to bisimilarity of states. This confirms that languages can be considered as the natural objects to describe the behaviour of automata. [Copyright &y& Elsevier]

Abstract: Many electoral control and manipulation problems—which we will refer to in general as “manipulative actions” problems—are NP-hard in the general case. It has recently been noted that many of these problems fall into polynomial time if the electorate is single-peaked, i.e., is polarized along some axis/issue. However, real-world electorates are not truly single-peaked. There are usually some mavericks, and so real-world electorates tend merely to be nearly single-peaked. This paper studies the complexity of manipulative-action algorithms for elections over nearly single-peaked electorates. We do this for many notions of nearness and for a broad range of election systems. We provide instances where even one maverick jumps the manipulative-action complexity up to NP-hardness, but we also provide many instances where some number of mavericks can be tolerated without increasing the manipulative-action complexity. [Copyright &y& Elsevier]

Abstract: Refinement is a relation on system models: a concrete model is a refinement of a more abstract model if it has fewer behaviors. When properties of the abstract model are guaranteed to be preserved in the concrete model, refinement supports a top-down development process. This paper considers preservation of a range of information flow security properties in synchronous systems with schedulers, when these schedulers are refined. Notions of refinement are defined for both an abstract notion of scheduler as well as for their concrete representation as automata. The security properties that are preserved by refinement over schedulers are then characterized. The results are applied to characterize a number of scheduler independent security properties, which state that a system is secure with respect to all schedulers. [Copyright &y& Elsevier]

Abstract: Looking for small universal computing devices is a natural and well investigated topic in computer science. Recently, this topic was also investigated in the framework of spiking neural P systems. One of the small universality results is that a small weakly universal extended spiking neural P system with 12 neurons was constructed. In this paper, a new way is introduced for simulating register machines by spiking neural P systems, where only one neuron is used for all instructions of the register machine; in this way, we can use less neurons to construct universal spiking neural P system. Specifically, we give a smaller weakly universal spiking neural P system that uses extended rules and has only 9 neurons. [Copyright &y& Elsevier]

Abstract: This paper continues the investigation of population P systems model [F. Bernardini, M. Gheorghe, Population P systems, Journal of Universal Computer Science 10 (5) (2004) 509–539] by considering bacterium quorum sensing (QS) phenomena as the basis of the new approach. A new computational model called QS P system is introduced. It is proved that QS P systems are able to simulate counter machines, and hence they are equivalent in power to Turing machines. An example of a QS P system modelling the behaviour of Vibrio fischeri bacteria colonies is also presented and the emergence of the QS mechanism is illustrated. [Copyright &y& Elsevier]