Abstract
This paper deals with the specification of software component protocols (i. e., the set of service call sequences). The contribution of this paper is twofold: (a) We discuss specific requirements of realworld protocols, especially in the presence of components which make use of limited resources. (b) We define counter-constrained finite state machines, a novel extension of finite state machines, specifically created to model protocols containing dependencies between services due to their access to shared resources. Opposed to other approaches like classical finite state machines, this newmo del combines two valuable properties: (a) it is powerful enough to model realistic component protocols with resource allocation, -usage, and -deallocation dependencies between methods (as occurring in common abstract data-types such as stacks or queues) and (b) allows effcient checking of interoperability and substitutability.
This work was undertaken while the author was with the Universität Karlsruhe (TH), Germany. It was supported by the Deutsche Forschungsgemeinschaft (DFG) (Graduiertenkolleg No. 209).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Robert Allen and David Garlan. A formal basis for architectural connection. ACM Transactions on Software Engineering and Methodology, 6(3):213–249, July 1997. 21
F. L. Bauer. The cellar principle of state transition and storage allocation. Annals of the History of Computing, 12(1):41–49, 1990. 27
Andrea Bracciali, Antonio Brogi, and Carlos Canal. Dynamically Adapting the Behaviour of Software Components. In Coordination, volume 2315 of Lecture Notes in Computer Science, pages 88–95. Springer-Verlag, Berlin, Germany, 2002. 24
Pŕemysl Brada. Towards automated component compatibility assessment. In Wolfgang Weck, Jan Bosch, and Clemens Szyperski, editors, Proceedings of the Sixth International Workshop on Component-Oriented Programming (WCOP’01), June 2001. 21
Luca de Alfaro and Thomas A. Henzinger. Interface automata. In Volker Gruhn, editor, Proceedings of the Joint 8th European Software Engeneering Conference and 9th ACM SIGSOFT Symposium on the Foundation of Software Engeneering (ESEC/FSE-01), volume 26, 5 of SOFTWARE ENGINEERING NOTES, pages 109–120, NewY ork, September 10-14 2001. ACM Press. 24
E. F. Moore. Gedanken-experiments on sequential machines. In C. E. Shannon and J. MacCarthy, editors, Automata Studies, pages 129–153, Princeton, New Jersey, 1956. Princeton University Press. 30, 34
Jürgen Freudig. Konformitötsprüfung jenseits von Typanalyse. Diplomarbeit, Fakultät für Informatik, Universität Karlsruhe (TH), Germany, September 1998. 36
Jun Han. Temporal logic based specification of component interaction protocols. In Proccedings of the 2nd Workshop of Object Interoperability at ECOOP 2000, Cannes, France, June 12.-16. 2000. 24, 36
Ken Higuchi, Mitsuo Wakatsuki, and Etsuji Tomita. A polynomial-time algorithm for checking the inclusion for real-time deterministic restricted one-counter automata which accept by accept mode. TIEICE: IEICE Transactions on Communications/ Electronics/Information and Systems, E81(1), 1998. 37
Gerald J. Holzmann. Design and Validation of Computer Protocols. Prentice Hall, Englewood Cliffs, NJ, USA, 1991. 24, 25, 36
J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, USA, 1979. 21, 23, 26, 33, 37
J. E. Hopcroft. An n log n algorithm for minimizing the states in a finiteautomaton. In Z. Kohavi, editor, Theory of Machines and Computations, pages 189–196. Academic Press, NewYork, NY, USA, 1971. 30
D.A. Huffman. The synthesis of sequential switching circuits. In Edward F. Moore (Ed.), Sequential Machines: Selected Papers. Addison-Wesley, Reading, MA, USA, 1964. 30, 34
Gunnar Hunzelmann. Generierung von Protokollinformation für Softwarekomponentenschnittstellen aus annotiertem Java-Code. Diplomarbeit, Fakultät für Informatik, Universität Karlsruhe (TH), Germany, April 2001. 23, 24
H.-A. Jacobsen and Bernd J. Krämer. Modeling interface definition language extensions. In IEEE Proceedings of TOOLS Pacific’ 00, Sydney, pages 242–252. IEEE Computer Society Press, 2000. 21, 37
Sun Microsystems Corp., The JAVA homepage. http://java.sun.com/. 22
S. C. Kleene. Representation of events in nerve nets and finite automata. In C. Shannon and J. McCarthy, editors, Automata Studies, Annals of Math. Studies 34, pages 3–40. Princeton, NewJersey, 1956. 24
Bernd Krämer. Synchronization constraints in object interfaces. In rnd Krämer, Michael P. Papazoglou, and Heinz W. Schnmidt, editors, Information Systems Interoperability, pages 111–141. Research Studies Press, Taunton, England, 1998. 21, 24, 37
Barbara H. Liskov and Jeannette M. Wing. A behavioral notion of subtyping. ACM Transactions on Programming Languages and Systems, 16(6):1811–1841, November 1994. 36
Zohar Manna and Amir Pnueli. The Temporal Logic of Reactive and Concurrent Systems. Springer-Verlag, NewYork, USA, 1992. 25, 36
Bertrand Meyer. Applying “design by contract”. IEEE Computer, 25(10):40–51, October 1992. 21
R. Milner. A calculus of communicating systems. Lecture Notes in Computer Science, 92, 1980. 36
Marvin Minsky. Computation: Finite and infinite machines. Prentice Hall, Englewood Cliffs, NJ, USA, 1972. 37
Oscar Nierstrasz. Regular types for active objects. In Proceedings of the 8th ACM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA-93), volume 28, 10 of ACM SIGPLAN Notices, pages 1–15, October 1993. 21, 24, 36
C. A. Petri. Fundamentals of a theory of asynchronous information flow. In Information Processing 62, pages 386–391. IFIP, North-Holland, 1962. 36
F. Plasil, S. Visnovsky, and M. Besta. Bounding component behavior via protocols. In Proceedings of TOOLS USA’ 99, pages 387–398. IEEE, August 1999. 21
W. Reisig. Petri Nets: An Introduction. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, Germany, 1985. 36
Ralf H. Reussner. Dynamic types for software components. In Companion of the Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA’ 99), November 5-10 1999. extended abstract. 21, 24
Ralf H. Reussner. Enhanced component interfaces to support dynamic adaption and extension. In 34th Hawaiin International Conference on System Sciences. IEEE, January 3-5 2001. 24
Ralf H. Reussner. Parametrisierte Verträge zur Protokolladaption bei SoftwareKomponenten. Logos Verlag, Berlin, 2001. 30
Ralf H. Reussner. Counter-Contraint Finite State Machines: Modelling Component Protocols with Resource-Dependencies. Technical Report 2002/121, School for Computer Science and Software Engineering, Monash University, VIC 3145 Australia, 2002. 21, 30
Arto Salomaa. Formal Languages. Academic Press, NewYork, NY, USA, 1973. 34
Heinz W. Schmidt and Ralf H. Reussner. Generating Adapters for Concurrent Component Protocol Synchronisation. In Proceedings of the Fifth IFIP International conference on Formal Methods for Open Object-based Distributed Systems, March 2002. 24
W.R. Stevens. TCP/IP Illustrated, Volume 1; The Protocols. Addison-Wesley, Reading, MA, USA, 1994. 24
Clemens Szyperski. Component Software: Beyond Object-Oriented Programming. ACM Press, Addison-Wesley, Reading, MA, USA, 1998. 20
Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., 2(42):230–265, 1936. 23
Leslie G. Valiant. Decision procedures for families of deterministic pushdown automata. Research Report CS-RR-001, Department of Computer Science, University of Warwick, Coventry, UK, August 1973. 37
Leslie G. Valiant. Regularity and related problems for deterministic pushdown automata. Journal of the ACM, 22(1):1–10, January 1975. 37
A. Vallecillo, J. Hernández, and J.M. Troya. Object interoperability. In A. Moreira and S. Demeyer, editors, ECOOP’ 99 Reader, number 1743 in LNCS, pages 1–21. Springer-Verlag, Berlin, Germany, 1999. 21, 36
W. M. P. van der Aalst, K. M. van Hee, and R.A. van der Toorn. Componentbased software architectures: A framework based on inheritance of behavior. BETA Working Paper Series WP 45, Eindhoven University of Technology, 2000. 36
D. Yellin and R. Strom. Protocol Specifications and Component Adaptors. ACM Transactions on Programming Languages and Systems, 19(2):292–333, 1997. 21, 24
AmyMoormann Zaremski and Jeannette M. Wing. Specification matching of software components. ACM Transactions on Software Engineering and Methodology, 6(4):333–369, October 1997. 36
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reussner, R. (2002). Counter-Constrained Finite State Machines: A New Model for Component Protocols with Resource-Dependencies. In: Grosky, W.I., Plášil, F. (eds) SOFSEM 2002: Theory and Practice of Informatics. SOFSEM 2002. Lecture Notes in Computer Science, vol 2540. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36137-5_2
Download citation
DOI: https://doi.org/10.1007/3-540-36137-5_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00145-4
Online ISBN: 978-3-540-36137-4
eBook Packages: Springer Book Archive