Search

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: 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: 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]