Fundamenta Informaticae - Volume 59, issue 1

Authors: Burton, Jonathan | Koutny, Maciej | Pappalardo, Giuseppe

Article Type: Research Article

Abstract: We present here an implementation relation intended to formalise the notion that a system built of communicating processes is an acceptable implementation of another base, or target, system in the event that the two systems have different interfaces. Such a treatment has clear applicability in the software development process, where (the interface of) an implementation component may be expressed at a different level of abstraction to (the interface of) the relevant specification component. Technically, processes are …formalised using Hoare's CSP language, with its standard failures-divergences model. The implementation relation is formulated in terms of failures and divergences of the implementation and target processes. Interface difference is modelled by endowing the implementation relation with parameters called extraction patterns. These are intended to interpret implementation behaviour as target behaviour, and suitably constrain the former in connection to well-formedness and deadlock properties. We extend the results of our previous work and replace implementation relations previously presented by a single, improved scheme. We also remove all the restrictions previously placed upon target processes. Two basic kinds of results are obtained: realisability and compositionality. The latter means that a target composed of several connected systems may be implemented by connecting their respective implementations. The former means that, if target and implementation in fact have the same interface, then the implementation relation they should satisfy collapses into standard implementation pre-order. We also show how to represent processes and extraction patterns in a manner amenable to computer implementation, and detail a graph-theoretic restatement of the conditions defining the implementation relation, from which algorithms for their automatic verification are easily derived. Show more

Keywords: theory of parallel and distributed computation, behaviour abstraction, refinement, communicating sequential processes, compositionality, verification,

Citation: Fundamenta Informaticae, vol. 59, no. 1, pp. 1-37, 2004

Authors: Ghosh, Sujata | Chakraborty, Mihir Kr.

Article Type: Research Article

Abstract: A general framework for the algebraization of a category of nonmonotonic logics has been suggested. This method has been applied to the systems of Gabbay, and to Cumulative, Preferential and Ranked systems. The minimal logics required to serve as the base logics for the above systems are investigated. MAK triples and KLM triples are formed in ways similar to MAK models and KLM models but now on the algebraic structures for the nonmonotonic systems, thereby a …new type of semantics is given to these systems. Show more

Keywords: nonmonotonic logic, algebraic semantics, cumulative system, preferential system, ranked system

Citation: Fundamenta Informaticae, vol. 59, no. 1, pp. 39-65, 2004

Authors: Jonoska, Nataša | Margenstern, Maurice

Article Type: Research Article

Abstract: In this paper we introduce a membrane system (named λP systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that λP systems can simulate pure λ-calculus and so they have universal computational power. We also show that NP-complete problems can be …solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input. Show more

Citation: Fundamenta Informaticae, vol. 59, no. 1, pp. 67-90, 2004

Authors: Terlikowski, Tomasz

Article Type: Research Article

Abstract: In this paper, we introduce the notion of risk-type description. The concept is strongly related to the definition of risk function, as analyzed in detail in [20]. The main difference consists in considering objects of other categories, different than those analyzed in [20]. The analysis shows relationships and differences between the two notions, both concerning the idea of risk in control.

Keywords: risk function, set theory, control variant, functional description, the concept of safety

Citation: Fundamenta Informaticae, vol. 59, no. 1, pp. 91-106, 2004