Labelled Transition System

14,000,000 Leading Edge Experts on the ideXlab platform

Scan Science and Technology

Contact Leading Edge Experts & Companies

Scan Science and Technology

Contact Leading Edge Experts & Companies

The Experts below are selected from a list of 282 Experts worldwide ranked by ideXlab platform

Raymond Devillers - One of the best experts on this subject based on the ideXlab platform.

  • Analysis and Synthesis of Weighted Marked Graph Petri Nets: Exact and Approximate Methods
    Fundamenta Informaticae, 2019
    Co-Authors: Raymond Devillers, Thomas Hujsa
    Abstract:

    Numerous real-world Systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a Labelled Transition System (lts) describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing Transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. We provide new behavioural properties of WMGs expressed on their reachability graph, notably backward persistence and strong similarities between any two sequences sharing the same starting state and the same destination state. Besides, we design a general synthesis procedure aiming at the WMG class. Finally, when no solution to the synthesis problem exists, i.e., when the given lts is not WMG-solvable, we show how to construct a WMG whose reachability graph is a minimal over-approximation of the given lts.

  • Petri Nets - Factorisation of Petri Net Solvable Transition Systems
    Application and Theory of Petri Nets and Concurrency, 2018
    Co-Authors: Raymond Devillers, Uli Schlachter
    Abstract:

    In recent papers, general conditions were developed to characterise when and how a Labelled Transition System may be factorised into non-trivial factors. These conditions combine a local property (strong diamonds) and a global one (separation), the latter being of course more delicate to check. Since one of the aims of such a factorisation was to speed up the synthesis of Petri nets from such Labelled Transition Systems, the problem arises to analyse if those conditions (and in particular the global one) could be simplified, or even dropped, in the special case of Petri net solvable behaviours, i.e., when Petri net synthesis is possible. This will be the subject of the present paper.

  • Analysis and Synthesis of Weighted Marked Graph Petri Nets
    2018
    Co-Authors: Raymond Devillers, Thomas Hujsa
    Abstract:

    Numerous real-world Systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a Labelled Transition System describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing Transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. To this end, we provide new conditions delineating more precisely their behaviour and give a dedicated synthesis procedure.

  • Characterisation of the state spaces of marked graph Petri nets
    Information and Computation, 2017
    Co-Authors: Eike Best, Raymond Devillers
    Abstract:

    The structure of the reachability graph of a marked graph Petri net is fully characterised. Exact structural conditions are given for a given Labelled Transition System to be generated by a marked graph. Two cases are distinguished, corresponding to the boundedness or the unboundedness of the net, and, respectively, to the finiteness or the infiniteness of the Transition System. Dedicated synthesis procedures are presented for both cases, and it is shown that there is always a unique minimal solution. The synthesis procedures allow this minimal net, its initial marking, and the marking bounds of its places to be computed from the Labelled Transition System.

Franck Van Breugel - One of the best experts on this subject based on the ideXlab platform.

Eike Best - One of the best experts on this subject based on the ideXlab platform.

  • Characterisation of the state spaces of marked graph Petri nets
    Information and Computation, 2017
    Co-Authors: Eike Best, Raymond Devillers
    Abstract:

    The structure of the reachability graph of a marked graph Petri net is fully characterised. Exact structural conditions are given for a given Labelled Transition System to be generated by a marked graph. Two cases are distinguished, corresponding to the boundedness or the unboundedness of the net, and, respectively, to the finiteness or the infiniteness of the Transition System. Dedicated synthesis procedures are presented for both cases, and it is shown that there is always a unique minimal solution. The synthesis procedures allow this minimal net, its initial marking, and the marking bounds of its places to be computed from the Labelled Transition System.

Alan Jeffrey - One of the best experts on this subject based on the ideXlab platform.

  • Contextual equivalence for higher-order pi-calculus revisited
    Logical Methods in Computer Science, 2005
    Co-Authors: Alan Jeffrey, Julian Rathke
    Abstract:

    The higher-order pi-calculus is an extension of the pi-calculus to allow communication of abstractions of processes rather than names alone. It has been studied intensively by Sangiorgi in his thesis where a characterisation of a contextual equivalence for higher-order pi-calculus is provided using Labelled Transition Systems and normal bisimulations. Unfortunately the proof technique used there requires a restriction of the language to only allow finite types. We revisit this calculus and offer an alternative presentation of the Labelled Transition System and a novel proof technique which allows us to provide a fully abstract characterisation of contextual equivalence using Labelled Transitions and bisimulations for higher-order pi-calculus with recursive types also.

  • MFPS - Contextual Equivalence for Higher-Order π-Calculus Revisited
    Electronic Notes in Theoretical Computer Science, 2003
    Co-Authors: Alan Jeffrey, Julian Rathke
    Abstract:

    The higher-order @p-calculus is an extension of the @p-calculus to allow communication of abstractions of processes rather than names alone. It has been studied intensively by Sangiorgi in his thesis where a characterisation of a contextual equivalence for higher-order @p-calculus is provided using Labelled Transition Systems and normal bisimulations. Unfortunately the proof technique used there requires a restriction of the language to only allow finite types. We revisit this calculus and offer an alternative presentation of the Labelled Transition System and a novel proof technique which allows us to provide a fully abstract characterisation of contextual equivalence using Labelled Transitions and bisimulations for higher-order @p-calculus with recursive types also.

  • a symbolic Labelled Transition System for coinductive subtyping of f_ mu leq types
    Logic in Computer Science, 2001
    Co-Authors: Alan Jeffrey
    Abstract:

    Abstract: F_\leq is a typed lambda-calculus with subtyping and bounded polymorphism. Typechecking for F_\leq is known to be undecidable, because the subtyping relation on types is undecidable. F_{\mu\leq} is an extension of F_\leq with recursive types. In this paper, we show how symbolic Labelled Transition System techniques from concurrency theory can be used to reason about subtyping for F_{\mu\leq}. We provide a symbolic Labelled Transition System for F_{\mu\leq} types, together with an an appropriate notion of simulation, which coincides with the existing coinductive definition of subtyping. We then provide a 'simulation up to' technique for proving subtyping, for which there is a simple model checking algorithm. The algorithm is more powerful than the usual one for F_\leq, for example it terminates on Ghelli's canonical example of nontermination.

  • LICS - A Symbolic Labelled Transition System for Coinductive Subtyping of F_{\mu\leq} Types
    2001
    Co-Authors: Alan Jeffrey
    Abstract:

    Abstract: F_\leq is a typed lambda-calculus with subtyping and bounded polymorphism. Typechecking for F_\leq is known to be undecidable, because the subtyping relation on types is undecidable. F_{\mu\leq} is an extension of F_\leq with recursive types. In this paper, we show how symbolic Labelled Transition System techniques from concurrency theory can be used to reason about subtyping for F_{\mu\leq}. We provide a symbolic Labelled Transition System for F_{\mu\leq} types, together with an an appropriate notion of simulation, which coincides with the existing coinductive definition of subtyping. We then provide a 'simulation up to' technique for proving subtyping, for which there is a simple model checking algorithm. The algorithm is more powerful than the usual one for F_\leq, for example it terminates on Ghelli's canonical example of nontermination.

Thomas Hujsa - One of the best experts on this subject based on the ideXlab platform.

  • Analysis and Synthesis of Weighted Marked Graph Petri Nets: Exact and Approximate Methods
    Fundamenta Informaticae, 2019
    Co-Authors: Raymond Devillers, Thomas Hujsa
    Abstract:

    Numerous real-world Systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a Labelled Transition System (lts) describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing Transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. We provide new behavioural properties of WMGs expressed on their reachability graph, notably backward persistence and strong similarities between any two sequences sharing the same starting state and the same destination state. Besides, we design a general synthesis procedure aiming at the WMG class. Finally, when no solution to the synthesis problem exists, i.e., when the given lts is not WMG-solvable, we show how to construct a WMG whose reachability graph is a minimal over-approximation of the given lts.

  • Analysis and Synthesis of Weighted Marked Graph Petri Nets
    2018
    Co-Authors: Raymond Devillers, Thomas Hujsa
    Abstract:

    Numerous real-world Systems can be modeled with Petri nets, which allow a combination of concurrency with synchronizations and conflicts. To alleviate the difficulty of checking their behaviour, a common approach consists in studying specific subclasses. In the converse problem of Petri net synthesis, a Petri net of some subclass has to be constructed efficiently from a given specification, typically from a Labelled Transition System describing the behaviour of the desired net. In this paper, we focus on a notorious subclass of persistent Petri nets, the weighted marked graphs (WMGs), also called generalised (or weighted) event (or marked) graphs or weighted T-nets. In such nets, edges have multiplicities (weights) and each place has at most one ingoing and one outgoing Transition. Although extensively studied in previous works and benefiting from strong results, both their analysis and synthesis can be further investigated. To this end, we provide new conditions delineating more precisely their behaviour and give a dedicated synthesis procedure.

Related terms

Labelled Transition System - 15 days free trial to Access Experts & Abstracts