On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs

• Autorzy: Esparza J. , Jančar P. , Miller A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Signal Transition Graphs (STGs); consistency; Complete State Coding; Petri net; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 86, nr 3
• Strony: 227--253
• Opis fizyczny: bibliogr. 17 poz. wykr.

Twórcy

autor

Esparza J.

autor

Jančar P.

autor

Miller A.

• Institut für Informatik, Technische Universität München, Germany,

Bibliografia

• [1] Carmona, J., Cortadella, J.: ILP Models for the Synthesis of Asynchronous Control Circuits, 2003 International Conference on Computer-Aided Design (ICCAD'03), November 9-13, 2003, San Jose, CA, USA, IEEE Computer Society / ACM, 2003, ISBN 1-58113-762-1.
• [2] 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.
• [3] Chu, T.-A.: Synthesis of Self-Timed VLSI Circuits from Graph-theoretic Specifications, Ph.D. Thesis, MIT, 1987.
• [4] Desel, J., Esparza, J.: Free Choice Petri Nets, vol. 40 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995.
• [5] Esparza, J.: Model checking using net unfoldings, Science of Computer Programming, 23, 1994, 151-195.
• [6] Esparza, J.: Decidability and Complexity of Petri Net Problems - an Introduction, Lectures on Petri Nets I: Basic Models. Advances in Petri Nets (G. Rozenberg, W. Reisig, Eds.), number 1491 in Lecture Notes in Computer Science, 1998.
• [7] Esparza, J.: A Polynomial-Time Algorithm for Checking Consistency of Free-Choice Signal Transition Graphs, Fundamenta Informaticae, 62(2), 2004, 197-220.
• [8] Esparza, J., Jančar, P., Miller, A.: On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs, Proceedings of the 6th International Conference on Application of Concurrency to System Design (ACSD 2006), IEEE Computer Society, Turku, Finland, June 2006.
• [9] Khomenko, V., Koutny, M., Yakovlev, A.: Detecting State Coding Conflicts in STGs Using Integer Programming, Proc. of the Design, Automation and Test in Europe Conference and Exhibition, IEEE Computer Society, 2002.
• [10] Khomenko, V., Koutny, M., Yakovlev, A.: Detecting State Coding Conflicts in STG Unfoldings using SAT, Proc. of the 4th Int. Conf. on Application of Concurrency to System Design, IEEE Computer Society, 2004.
• [11] Pastor, E., Cortadella, J.: Polynomial algorithms for the synthesis for hazard-free circuits from signal transition graphs, 1993 International Conference on Computer-Aided Design (ICCAD'93), Santa Clara, CA, USA, IEEE Computer Society / ACM, 1993.
• [12] Rosenblum, L., Yakovlev, A.: Signal Graphs: from self-timed to timed ones, Proc. Int. Workshop on Timed Petri nets, IEEE Computer Society, 1985.
• [13] Schrijver, A.: Theory of Linear and Integer Programming, Wiley, 1986.
• [14] Vanbekbergen, P., Catthoor, F., Goossens, G., Man, H. D.: Optimized synthesis of asynchronous control circuits from graph-theoretic specifications, 1990 International Conference on Computer-Aided Design (ICCAD'90), IEEE Computer Society, 1990.
• [15] Yamasaki, H., Huang, J., Murata, T.: Reachability Analysis of Petri Nets via Structural and behavioral Classifications of Transitions, Petri Net Newsletter, (60), 2001, 5-21.
• [16] Ykman-Couvreur, C., Lin, B., Goossens, G., Man, H. D.: Synthesis and optimization of asynchronous controllers based on extended lock graph theory, 4th European Conference on Design Automation, Paris, France, IEEE Computer Society, 1993.
• [17] Yu,M., Subrahmanyam, P.: A new approach for checking the unique state coding property of signal transition graphs, Proc. 3rd Int. European Conference on Design Automation, IEEE Computer Society, 1992.