1787436
Proving termination of membership equational programs
Advanced typing, matching, and evaluation strategy features, as well as very general conditional rules, are routinely used in equational programming languages such as, for example, <sc>ASF+SDF</sc>, <sc>OBJ</sc>, <sc>CafeOBJ</sc>, <sc>Maude</sc>, and equational subsets of <sc>ELAN</sc> and <sc>CASL</sc>. Proving termination of equational programs having such expressive features is important but nontrivial, because some of those features may not be supported by standard termination methods and tools, such as <sc>muterm</sc>, <sc>C<i>i</i>ME</sc>, <sc>AProVE</sc>, <sc>TTT</sc>, <sc>Termptation</sc>, etc. Yet, use of the features may be essential to ensure termination. We present a sequence of theory transformations that can be used to bridge the gap between expressive equational programs and termination tools, prove the correctness of such transformations, and discuss a prototype tool performing the transformations on <sc>Maude</sc> equational programs and sending the resulting transformed theories to some of the aforementioned tools.
14145609
Functorial semantics for Petri nets under the individual token philosophy
Although the algebraic semantics of place/transition Petri nets under the collective token philosophy has been fully explained in terms of (strictly) symmetric (strict) monoidal categories, the analogous construction under the individual token philosophy is not completely satisfactory because it lacks universality and also functoriality. We introduce the notion of pre-net to recover these aspects, obtaining a fully satisfactory categorical treatment centered on the notion of adjunction. This allows us to present a purely logical description of net behaviours under the individual token philosophy in terms of theories and theory morphisms in partial membership equational logic, yielding a complete match with the theory developed by the authors for the collective token view of nets
1049616
On the Semantics of Place/Transition Petri Nets
Placestransition (PT) Petri nets are one of the most widely used models of concurrency. However, they still lack, in our view, a satisfactory semantics: on the one hand the ‘token game’ is too intensional, even in its more abstract interpretations in terms of nonsequential processes and monoidal categories; on the other hand, Winskel's basic unfolding construction, which provides a coreflection between nets and finitary prime algebraic domains, works only for safe nets. In this paper we extend Winskel's result to PT nets. We start with a rather general category PTNets of PT nets, we introduce a category DecOcc of decorated (nondeterministic) occurrence nets and we define adjunctions between PTNets and DecOcc and between DecOcc and Occ, the category of occurrence nets. The role of DecOcc is to provide natural unfoldings for PT nets, i.e., acyclic safe nets where a notion of family is used to relate multiple instances of the same place. The unfolding functor from PTNets to Occ reduces to Winskel's when restricted to safe nets. Moreover, the standard coreflection between Occ and Dom, the category of finitary prime algebraic domains, when composed with the unfolding functor above, determines a chain of adjunctions between PTNets and Dom.
1768436
Modular Rewriting Semantics in Practice
We present a general method to achieve modularity of semantic definitions of programming languages specified as rewrite theories, so that semantic rules do not have to be redefined in language extensions. We illustrate the practical use of this method by means of two language case studies: two different semantics for CCS, and three different semantics for the GNU bc language.
1438509
Algebraic Theories for Contextual Pre-nets
The algebraic models of computation for contextual nets that have been proposed in the literature either rely on a non-free monoid of objects, or introduce too many fictitious behaviors that must be somewhat filtered out. In this paper, we exploit partial membership equational logic to define a suitable theory of models, where the meaningful concurrent computations can be selected by means of membership predicates.
2005628
The Maude LTL Model Checker and Its Implementation
A model checker typically supports two different levels of specification: (1) a system specification level, in which the concurrent system to be analyzed is formalized; and (2) a property specification level, in which the properties to be model checked—for example, temporal logic formulae—are specified. The Maude LTL model checker has been designed with the goal of combining a very expressive and general system specification language (Maude [1]) with an advanced on-the-fly explicit-state LTL model checking engine.
15142775
Unwinding and Inference Control
This paper discusses two main ideas, unwinding and inference control. While both concern computer security, they are not closely related to each other. Unwinding is a verification technique for general security requirements based on noninterference assertions as in [Goguen & Meseguer 82a]. The inference control problem concerns preventing inference of unauthorized information by combining authorized information. The main result in this paper is an unwinding theorem that gives a very simple necessary and sufficient condition for a system to satisfy the MLS security policy system. A subsidiary topic is secure interfaces, which we show how to treat with noninterferce assertions.