nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Kleene Theorems for Synchronous Products with Matching

verfasst von : Ramchandra Phawade, Kamal Lodaya

Erschienen in: Transactions on Petri Nets and Other Models of Concurrency X

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In earlier work [LMP11], we showed that a graph-theoretic condition called “structural cyclicity” enables us to extract syntax from a conflict-equivalent product system of automata. In this paper we have a “pairing” property in our syntax which allows us to connect to a broader class of synchronous product systems [Arn94] with a “matching” property, where the conflict-equivalence is not statically fixed. These systems have been related to labelled free choice nets.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel SMT-Based Abstract Parametric Temporal Planning

Nächstes Kapitel Symbolic Model Checking of Security Protocols for Ad hoc Networks on any Topologies

A preliminary version of this paper appeared at the 8th PNSE workshop in Tunis [PL14]. We thank the organizers for all the help provided for the presentation.

[Ant96]

Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155(2), 291–319 (1996)MathSciNetCrossRefMATH

[Arn94]

Arnold, A.: Finite Transition Systems. Prentice-Hall, UK (1994)

[Brz64]

Brzozowski, J.A.: Derivatives of regular expressions. JACM 11(4), 481–494 (1964)MathSciNetCrossRefMATH

[DE95]

Desel, J., Esparza, J.: Free Choice Petri Nets. Cambridge University Press, New York (1995)CrossRefMATH

[GR92]

Garg, V.K., Ragunath, M.T.: Concurrent regular expressions and their relationship to Petri nets. Theor. Comput. Sci. 96(2), 285–304 (1992)MathSciNetCrossRefMATH

[Gra81]

Grabowski, J.: On partial languages. Fund. Inform. IV(2), 427–498 (1981)MathSciNetMATH

[Hac72]

Hack, M.H.T.: Analysis of production schemata by Petri nets. Project Mac report TR-94. MIT (1972)

[LMP11]

Lodaya, K., Mukund, M., Phawade, R.: Kleene theorems for product systems. In: Holzer, M., Kutrib, M., Pighizzini, G. (eds.) DCFS 2011. LNCS, vol. 6808, pp. 235–247. Springer, Heidelberg (2011) CrossRef

[LRR03]

Lodaya, K., Ranganayakulu, D., Rangarajan, K.: Hierarchical structure of 1-safe petri nets. In: Saraswat, V.A. (ed.) ASIAN 2003. LNCS, vol. 2896, pp. 173–187. Springer, Heidelberg (2003) CrossRef

[LS05]

Lombardy, S., Sakarovitch, J.: How expressions can code for automata. RAIRO Theor. Inform. Appl. 39(1), 217–237 (2005)MathSciNetCrossRefMATH

[LS10]

Lombardy, S., Sakarovitch, J.: Corrigendum. RAIRO Theor. Inform. Appl. 44(3), 339–361 (2010)MathSciNetCrossRefMATH

[LW00]

Lodaya, K., Weil, P.: Series-parallel languages and the bounded width property. Theor. Comput. Sci. 237(1–2), 347–380 (2000)MathSciNetCrossRefMATH

[Mir66]

Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 110–116 (1966)

[MR02]

Mohalik, S., Ramanujam, R.: Distributed automata in an assumption-commitment framework. Sādhanā 27(Part 2), 209–250 (2002)MathSciNetMATH

[Muk11]

Mukund, M.: Automata on distributed alphabets. In: D’Souza, D., Shankar, P. (eds.) Modern Applications of Automata Theory, pp. 257–288. World Scientific, Singapore (2011)

[MY60]

McNaughton, R., Yamada, H.: Regular expressions and state graphs for automata. IEEE Trans. IRS EC–9, 39–47 (1960)MATH

[Pha14a]

Phawade, R.: Direct product representation of labelled free choice nets. Int. J. Comput. Appl. 99(16), 1–8 (2014)

[Pha14b]

Phawade, R.: Labelled Free Choice Nets, finite Product Automata, and Expressions. Ph.D. thesis, Homi Bhabha National Institute (2014, submitted)

[PL14]

Phawade, R., Lodaya, K.: Kleene theorems for labelled free choice nets. In: Proceedings of the 8th PNSE. CEUR-WS, Tunis, vol. 1160, pp. 75–89 (2014)

[SH96]

Straub, P.A., Carlos Hurtado, L.: Business process behaviour is (almost) free-choice. In: Proceedings of CESA, Lille, pp. 9–12. IEEE (1996)

[TY14]

Thiagarajan, P.S., Yang, S.: Rabin’s theorem in the concurrency setting: a conjecture. Theor. Comput. Sci. 546, 225–236 (2014)MathSciNetCrossRefMATH

[Zie87]

Zielonka, W.: Notes on finite asynchronous automata. Inform. Theor. Appl. 21(2), 99–135 (1987)MathSciNetCrossRefMATH

Titel: Kleene Theorems for Synchronous Products with Matching
verfasst von: Ramchandra Phawade
Kamal Lodaya
Verlag: Springer Berlin Heidelberg
Buch: Transactions on Petri Nets and Other Models of Concurrency X
Print ISBN: 978-3-662-48649-8

Electronic ISBN: 978-3-662-48650-4

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-662-48650-4_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"