Fundamenta Informaticae - Volume 86, issue 3

Article Type: Other

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. i-ii, 2008

Authors: Esparza, Javier | Jančar, Petr | Miller, Alexander

Article Type: Research Article

Abstract: Signal Transition Graphs (STGs) are a popular formalism for the specification of asynchronous circuits. A necessary condition for the implementability of an STG is the existence of a consistent and complete state encoding. For an important subclass of STGs, the marked graph STGs, we show that checking consistency is polynomial, but checking the existence of a complete state coding is co-NP-complete. In fact, co-NP-completeness already holds for acyclic and 1-bounded marked graph STGs and for live …and 1-bounded marked graph STGs. We add some relevant results for free-choice, bounded, and general STGs. Show more

Keywords: signal transition graphs, consistency, complete state coding, Petri nets, complexity

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. 227-253, 2008

Authors: Juhás, Gabriel | Lorenz, Robert | Mauser, Sebastian

Article Type: Research Article

Abstract: In this paper, we show how to obtain causal semantics distinguishing "earlier than" and "not later than" causality between events from algebraic semantics of Petri nets. Janicki and Koutny introduced so called stratified order structures (so-structures) to describe such causal semantics. To obtain algebraic semantics, we redefine our own algebraic approach generating rewrite terms via partial operations of synchronous composition, concurrent composition and sequential composition. These terms are used to produce so-structures which …define causal behavior consistent with the (operational) step semantics. For concrete Petri net classes with causal semantics derived from processes minimal so-structures obtained from rewrite terms coincide with minimal so-structures given by processes. This is demonstrated for elementary nets with inhibitor arcs. Show more

Keywords: theory of concurrency, algebraic Petri nets, causal semantics, process terms, inhibitor arcs, synchronicity

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. 255-298, 2008

Authors: Khomenko, Victor | Madalinski, Agnes | Yakovlev, Alex

Article Type: Research Article

Abstract: A combined framework for the resolution of encoding conflicts in STG unfoldings is presented, which extends previouswork by incorporating concurrency reduction in addition to signal insertion. Furthermore, a novel validity condition is proposed to justify these transformations. The method has been implemented in the CONFRES tool and applied to a number of case studies. The experimental results show that the combined framework enlarges the design space and allows for better exploration of the speed/area tradeoff.

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. 299-323, 2008

Authors: Liu, Cong | Kondratyev, Alex | Watanabe, Yosinori | Desel, Jörg | Sangiovanni-Vincentelli, Alberto

Article Type: Research Article

Abstract: A schedule of a Petri Net (PN) represents a set of firing sequences that can be infinitely repeated within a bounded state space, regardless of the outcomes of the nondeterministic choices. Schedulability analysis for a given PN answers the question whether a schedule exists in the reachability space of this net. This paper suggests a novel approach for schedulability analysis based solely on PN structure. It shows that unschedulability can be caused by a structural relation …among transitions modelling nondeterministic choices. A method based on linear programming for checking this relation is proposed. This paper also presents a necessary condition for schedulability based on the rank of the incidence matrix of the underlying PN. These results shed a light on the sources of unschedulability often found in PN models of embedded multimedia systems. Show more

Keywords: Petri net, structural property, quasi-static scheduling

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. 325-341, 2008

Authors: Seceleanu, Tiberiu | Jantsch, Axel

Article Type: Research Article

Abstract: A deterministic behavior of systems composed of several modules is a desirable design goal. Assembling a complex system from components requires also a high degree of re-usability. The compatibility of the selected components may become a problem even at abstract design levels, due to possible different degrees of model determinacy, possible different execution models, etc. In this cases, an overall deterministic system behavior is difficult to achieve. The development of communication mechanisms between such components …will have then to accommodate the differences, so that both correct processing and information exchange (data and control, appropriate choices and relative timing or sequencing) are achieved. For instance, human-machine interaction offers a good example of cooperation between deterministic models (machines) communicatingwith highly non-deterministic counterparts (the human models, if not restricted). We analyze here such communication mechanisms by "confronting" synchronized and un-synchronized models of execution, in the framework of action systems, a state based formalism. We "force" the two models to coexist within the same context and explore the possibilities of building trustworthy communication channels between them. We base our approach on a combined polling - interrupt scheme, which allows us to mitigate communication issues that may otherwise compromise the correct input-output system behavior. More robust system models are obtained by applying specific correctness rules of refinement. We illustrate our methods on an audio system example, implementable as either a software or a hardware device. Show more

Keywords: System modeling, synchronized / interleaved communication, action systems

Citation: Fundamenta Informaticae, vol. 86, no. 3, pp. 343-369, 2008