iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-642-27269-1_14
Decomposition of Constraint Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Decomposition of Constraint Automata

  • Conference paper
Formal Aspects of Component Software (FACS 2010)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 6921))

Included in the following conference series:

Abstract

Reo is a coordination language that can be used to model different systems. Constraint automata form a formal semantics for Reo connectors based on a co-algebraic model of streams. In this paper, we introduce complete constraint automata (CCA) whose extra information about entropy states helps in analyzing and decomposing them into Reo circuits. We show that a complete constraint automaton is invertible. This property helps to partition and decompose a constraint automaton, a process which can be utilized to synthesize Reo circuits from constraint automata, automatically.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Arbab, F.: Reo: a channel-based coordination model for component composition. Mathematical Structures in Computer Science 14, 329–366 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arbab, F., Baier, C., Rutten, J.J.M.M., Sirjani, M.: Modeling component connectors in Reo by constraint automata (extended abstract). Electr. Notes Theor. Comput. Sci. 97, 25–46 (2004)

    Article  MATH  Google Scholar 

  3. Mehta, N.R., Medvidovic, N., Sirjani, M., Arbab, F.: Modeling behavior in compositions of software architectural primitives. In: ASE, pp. 371–374. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  4. Razavi, N., Sirjani, M.: Using Reo for formal specification and verification of system designs. In: MEMOCODE, pp. 113–122. IEEE, Los Alamitos (2006)

    Google Scholar 

  5. Meng, S., Arbab, F.: Web services choreography and orchestration in Reo and constraint automata. In: Cho, Y., Wainwright, R.L., Haddad, H., Shin, S.Y., Koo, Y.W. (eds.) SAC, pp. 346–353. ACM, New York (2007)

    Google Scholar 

  6. Arbab, F., Rutten, J.J.M.M.: A coinductive calculus of component connectors. In: Wirsing, M., Pattinson, D., Hennicker, R. (eds.) WADT 2003. LNCS, vol. 2755, pp. 34–55. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  7. Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1, 131–137 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  8. Krohn, K., Rhodes, J.: Algebraic theory of machines. I. prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society, vol. 116, pp. 450–464. ACM, New York (1965)

    MATH  Google Scholar 

  9. Eilenberg, S.: Automata, languages and machines (1976)

    Google Scholar 

  10. Egri-Nagy, A., Nehaniv, C.L.: Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes theory. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 315–316. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  11. Schützenberger, M.: On the definition of a family of automata. Information and Control, 245–270 (1961)

    Google Scholar 

  12. Kozen, D.: On Kleene algebras and closed semirings. In: Proc. Mathematical Foundations in Computer Science, vol. 452, pp. 26–47 (1990)

    Google Scholar 

  13. Arbab, F., Baier, C., de Boer, F.S., Rutten, J.J.M.M., Sirjani, M.: Synthesis of Reo circuits for implementation of component-connector automata specifications. In: Jacquet, J.M., Picco, G.P. (eds.) COORDINATION 2005. LNCS, vol. 3454, pp. 236–251. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  14. Koehler, C., Clarke, D.: Decomposing port automata. In: Shin, S.Y., Ossowski, S. (eds.) SAC, pp. 1369–1373. ACM, New York (2009)

    Google Scholar 

  15. Vuillemin, J., Gama, N.: Compact normal form for regular languages as xor automata. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol. 5642, pp. 24–33. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AmirKabir University, Tehran, Iran

    Bahman Pourvatan

  2. LIACS, Leiden University, Leiden, The Netherlands

    Bahman Pourvatan, Farhad Arbab & Marcello M. Bonsangue

  3. Reykjavik University, Reykjavik, Iceland

    Marjan Sirjani

  4. University of Tehran, Tehran, Iran

    Marjan Sirjani

  5. CWI, Amsterdam, The Netherlands

    Farhad Arbab & Marcello M. Bonsangue

Authors
  1. Bahman Pourvatan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marjan Sirjani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Farhad Arbab
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marcello M. Bonsangue
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. HASLab (High Assurance Software Laboratory) and Dept. of Informatics, Universidade do Minho, Campus de Gualtar, 4700-320, Braga, Portugal

    Luís Soares Barbosa

  2. Faculty of Information and Communication Technologies, Swinburne University of Technology, P.O. Box 218, 3122, Hawthorn, VIC, Australia

    Markus Lumpe

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Pourvatan, B., Sirjani, M., Arbab, F., Bonsangue, M.M. (2012). Decomposition of Constraint Automata. In: Barbosa, L.S., Lumpe, M. (eds) Formal Aspects of Component Software. FACS 2010. Lecture Notes in Computer Science, vol 6921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27269-1_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27269-1_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-27268-4

  • Online ISBN: 978-3-642-27269-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation