The week's pick
Reseach Article
Direct Product Representation of Labelled Free Choice Nets
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 99 - Number 16 |
| Year of Publication: 2014 |
| Authors: Ramchandra Phawade |
10.5120/17454-8313
|
Ramchandra Phawade . Direct Product Representation of Labelled Free Choice Nets. International Journal of Computer Applications. 99, 16 ( August 2014), 1-8. DOI=10.5120/17454-8313
Abstract
Hack's theorem [7] shows that every live and bounded free choice net is covered by S-components [5, 2]. If the net is labelled, with a distribution of the alphabet into possibly overlapping subalphabets for components, the question arose whether the net can be decomposed into a product of automata, with several possible definitions of product and of equivalence [1, 13, 11, 4]. Zielonka showed [15] that there is a live and 1- bounded net which is not direct product representable. We give a straightforward example of a live and 1-bounded labelled free choice net which is not direct product representable, we do not know of any earlier such example. We give two sufficient conditions for 1-bounded labelled free choice nets to be direct product representable. In the other direction, we give two sufficient conditions on products of automata using which we can construct labelled free choice nets. In [14] expressions corresponding to such products has been recently given.
References
- Andr´e Arnold (1994): Finite transition systems. Prentice Hall.
- Sandie Balaguer, Thomas Chatain & Stefan Haar (2012): A concurrency-preserving translation from time Petri nets to networks of timed automata. Formal Meth. Sys. Des. 40(3), pp. 330–355. Available at http://dx. doi. org/10. 1007/ s10703-012-0146-4.
- Roy H. Campbell & A. Nico Habermann (1974): The specification of process synchronization by path expressions. In: Proc. Operating Systems conference, Rocquencourt, LNCS 16, Springer, pp. 89–102.
- Ilaria Castellani, Madhavan Mukund & P. S. Thiagarajan (1999): Synthesizing distributed transition systems from global specifications. In C. Pandu Rangan, Venkatesh Raman & R. Ramanujam, editors: Proc. 19th FSTTCS, Chennai, LNCS 1738, Springer, pp. 219–231. Available at http: //dx. doi. org/10. 1007/3-540-46691-6_17.
- J¨org Desel & Javier Esparza (1995): Free choice Petri nets. Cambridge University Press, New York, USA.
- Volkert Diekert & Grzegorz Rozenberg, editors (1995): The book of traces. World Scientific, River Edge, NJ, USA.
- Michel Henri Th´eodore Hack (1972): Analysis of production schemata by Petri nets. Project Mac Report TR-94, MIT.
- Charles Antony Richard Hoare (1985): Communicating sequential processes. Prentice-Hall.
- Kamal Lodaya (2006): Product automata and process algebra. In: Proc. 4th SEFM, Pune, IEEE, pp. 128–136.
- Kamal Lodaya, Madhavan Mukund & Ramchandra Phawade (2011): Kleene theorems for product systems. In Markus Holzer, Martin Kutrib & Giovanni Pighizzini, editors: Proc. 13th DCFS, Limburg, LNCS 6808, pp. 235–247.
- Swarup Mohalik & R. Ramanujam (2002): Distributed automata in an assumption-commitment framework. S—adhan—a 27, part 2, pp. 209–250.
- Madhavan Mukund (2011): Automata on distributed alphabets. In Deepak D'Souza & Priti Shankar, editors: Modern applications of automata theory, World Scientific, pp. 257– 288.
- Madhavan Mukund & Milind A. Sohoni (1997): Keeping track of the latest gossip in a distributed system. Distrib. Comp. 10(3), pp. 117–127.
- Ramchandra Phawade & Kamal Lodaya (2014): Kleene theorems for labelled free choice nets. In: Proc. 8th PNSE, Tunis, CEUR-WS, pp. 75–89.
- Wies³aw Zielonka (1987): Notes on finite asynchronous automata. Inform. Theor. Appl. 21(2), pp. 99–135.
Index Terms
Keywords