Czasopismo
2004
|
Vol. 62, nr 2
|
197--220
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Warianty tytułu
Konferencja
Third International Conference on Application of Concurrency to System Design (ACSD'03) (18-20 June, 2003, Guimaraes, Portugal)
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
197--220
Opis fizyczny
Bibliogr. 22 poz., wykr.
Twórcy
autor
- Institute for Formal Methods in Computer Science, University of Stuttgart, Germany, esparza@informatik.uni-stuttgart.de
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0005-0078