A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs

• Autorzy: Esparza, J.
• Konferencja: Third International Conference on Application of Concurrency to System Design (ACSD'03) (18-20 June, 2003, Guimaraes, Portugal)
• Języki publikacji: EN

Abstrakty

EN

Signal Transition Graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Deciding this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analizability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. This paper presents the first polynomial algorithm for checking consistency.

Słowa kluczowe

EN

free choice Petri nets; Signal Transition Graphs; STGs

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 2
• Strony: 197--220
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Esparza, J.

• Institute for Formal Methods in Computer Science, University of Stuttgart, Germany,

Bibliografia

• [1] van der Aalst, W.: The Application of Petri Nets to Workflow Management, The Journal of Circuits, Systems and Computers, 8(1), 1998,21-66.
• [2] van Berkel, C, Josephs, M., Nowick, S.: Scanning the Technology: Applications of Asynchronous Circuits, Proceedings of the IEEE. 87(2), 1999, 234-242.
• [3] Carmona, J., Cortadella, J., Pastor, E.: A structural encoding technique for the synthesis of asynchronous circuits, Proc. Int. Conf. on Application of Concurrency Theory to System Design, IEEE Computer Society, 2001.
• [4] Chu, T.-A.: On the models for designing VLSI asynchronous digital systems. Integration: the VLSI journal, 4, 1986,99-113.
• [5] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-theoretic Specifications, Ph.D. Thesis, MIT, 1987.
• [6] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool for manipulating concurrent specifications and synthesis of asynchronous controllers, lElCE Trans, on Information and Systems, E80-D(3), 1997, 315-325.
• [7] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Logic synthesis of asynchronous controllers and interfaces. Springer-Verlag, 2002.
• [8] Cortes, L.: Private communication, 2002.
• [9] Desel, J., Esparza, J.: Free Choice Petri Nets, vol. 40 oi Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995.
• [10] Esparza, J.: Reduction and Synthesis of Live and Bounded Free Choice Petri Nets, Information and Computation, 114(1),1994, 50-87.
• [11] Esparza, J.: Decidability and complexity of Petri net problems - an introduction, in: Lectures on Petri Nets I: Basic Models. Advances in Petri Nets, vol. 1491 of Lecture Notes in Computer Science, Springer-Verlag, 1998,374^28.
• [12] Kondratyev, A., Cortadella, J., Kishinevsky. M., Pastor, E., Roig, O., Yakovlev, A.: Checking Signal Transition Graph implementability by Symbolic BDD Traversal, Proc. European Design and Test Conference, 1995.
• [13] Kovalyov, A.: Concurrency Relations and the Safety Problem for Petri Nets, in: Proc. I3th Int. Conf on Application and Theory of Petri Nets, vol. 616 of Lecture Notes in Computer Science, 1992, 299-309.
• [14] Kovalyov, A., Esparza, J.: A Polynomial Algorithm to Compute the Concurrency Relation of Free-choice Signal Transition Graphs, Proc. Int. Workshop on Discrete Event Systems, IEE Society, 1996.
• [15] Landweber, L., Robertson, E.: Properties of Conflict-Free and Persistent Petri Nets, Journal of the ACM, 25(3), 1978,352-364.
• [16] Lavagno, L., Moon, C, Brayton, R., Sangiovanni-Vincentelli, A.: Solving the state assignment problem for signal transition graphs, Proc. 29th IEEE/ACM Design Automation Conference, IEEE Computer Society Press, 1992.
• [17] Lipton, R.: The Reachability Problem Requires Exponential Space, Technical Report 62, Yale University, 1976.
• [18] Pastor, E., Cortadella, J., Kondratyev, A., Roig, O.: Structural Methods for the Synthesis of Speed Independent Circuits, IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, 17(11), 1998, 1108-1129.
• [19] Reisig, W.: Petri Nets: An Introduction, vol. 4 of EATCS Monographs in Computer Science, Springer-Verlag, 1985.
• [20] Rosenblum, L., Yakovlev. A.: Signal Graphs: from self-timed to timed ones, Proc. Int. Workshop on Timed Petri nets, IEEE Computer Society, 1985.
• [21] Vanbekbergen, P., Goosens, G., Catthoor, R. Man. H. D.: Optimized Synthesis of Asynchronous Control Circuits from Graph-Theoretic Specifications, lEEE Trans. on Computer Aided Design, 11(11), 1992, 1426-1438.
• [22] Vanbekbergen. P., Lin. B. Goosens, G, Man, H. D: A generalized state assignment theory for transformations on signal transition graphs, Proc. Int. Conf. on Computer Aided Design, 1992.