CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Direct Product Representation of Labelled Free Choice Nets

by Ramchandra Phawade
journal cover thumbnail

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

@article{ 10.5120/17454-8313,
author = { Ramchandra Phawade },
title = { Direct Product Representation of Labelled Free Choice Nets },
journal = { International Journal of Computer Applications },
issue_date = { August 2014 },
volume = { 99 },
number = { 16 },
month = { August },
year = { 2014 },
issn = { 0975-8887 },
pages = { 1-8 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume99/number16/17454-8313/ },
doi = { 10.5120/17454-8313 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:28:20.737199+05:30
%A Ramchandra Phawade
%T Direct Product Representation of Labelled Free Choice Nets
%J International Journal of Computer Applications
%@ 0975-8887
%V 99
%N 16
%P 1-8
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Andr´e Arnold (1994): Finite transition systems. Prentice Hall.
  2. 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.
  3. 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.
  4. 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.
  5. J¨org Desel & Javier Esparza (1995): Free choice Petri nets. Cambridge University Press, New York, USA.
  6. Volkert Diekert & Grzegorz Rozenberg, editors (1995): The book of traces. World Scientific, River Edge, NJ, USA.
  7. Michel Henri Th´eodore Hack (1972): Analysis of production schemata by Petri nets. Project Mac Report TR-94, MIT.
  8. Charles Antony Richard Hoare (1985): Communicating sequential processes. Prentice-Hall.
  9. Kamal Lodaya (2006): Product automata and process algebra. In: Proc. 4th SEFM, Pune, IEEE, pp. 128–136.
  10. 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.
  11. Swarup Mohalik & R. Ramanujam (2002): Distributed automata in an assumption-commitment framework. S—adhan—a 27, part 2, pp. 209–250.
  12. Madhavan Mukund (2011): Automata on distributed alphabets. In Deepak D'Souza & Priti Shankar, editors: Modern applications of automata theory, World Scientific, pp. 257– 288.
  13. Madhavan Mukund & Milind A. Sohoni (1997): Keeping track of the latest gossip in a distributed system. Distrib. Comp. 10(3), pp. 117–127.
  14. Ramchandra Phawade & Kamal Lodaya (2014): Kleene theorems for labelled free choice nets. In: Proc. 8th PNSE, Tunis, CEUR-WS, pp. 75–89.
  15. Wies³aw Zielonka (1987): Notes on finite asynchronous automata. Inform. Theor. Appl. 21(2), pp. 99–135.
Index Terms

Computer Science
Information Sciences

Keywords

Petri nets Kleene Theorem Direct Products Synchronization Traces

Powered by PhDFocusTM