Shuffle languages, Petri nets, and context-sensitive grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shuffle languages, Petri nets, and context-sensitive grammars

Full text

Pdf (865 KB)

Source

Communications of the ACM archive
Volume 24 , Issue 9 (September 1981) table of contents

Pages: 597 - 605

Year of Publication: 1981

ISSN:0001-0782

Author

Jay Gischer

Univ. of Washington, Seattle

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 50, Citation Count: 8

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358746.358767 What is a DOI?

ABSTRACT

Flow expressions have been proposed as an extension of the regular expressions designed to model concurrency. We examine a simplification of these flow expressions which we call shuffle expressions. We introduce two types of machines to aid in recognizing shuffle languages and show that one such machine may be equivalent to a Petri Net. In addition, closure and containment properties of the related language classes are investigated, and we show that one machine type recognizes at least a restricted class of shuffle languages. Finally, grammars for all shuffle languages are generated, and the shuffle languages are shown to be context-sensitive.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Araki, T., Kagimasa, T., and Tokura, N. Relations of flow languages to Petri Net languages. Programming Languages Group Memo No. 79-01, Dept of Infor. and Comp. Sci., Osaka, Japan, Feb. 1979.
	2	Seymour Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, Inc., New York, NY, 1966
	3	M. Hack, PETRI NET LANGUAGE, Massachusetts Institute of Technology, Cambridge, MA, 1976
	4	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	5	Shaw, A. C., Software descriptions with flow expressions. IEEE Trans. Software Eng. SE-4, 3, (May 1978) 243-254.

CITED BY 8

	Atsushi Igarashi , Naoki Kobayashi, Resource usage analysis, ACM SIGPLAN Notices, v.37 n.1, p.331-342, Jan. 2002
	Atsushi Igarashi , Naoki Kobayashi, Resource usage analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.2, p.264-313, March 2005
	Maurice H. ter Beek , Carlos Martín-Vide , Victor Mitrana, Synchronized shuffles, Theoretical Computer Science, v.341 n.1, p.263-275, 5 September 2005
	Maurice H. ter Beek , Jetty Kleijn, Infinite unfair shuffles and associativity, Theoretical Computer Science, v.380 n.3, p.401-410, June, 2007
	Florin Manea , Victor Mitrana , Daniel-Claudian Voinescu, Synchronized Shuffle on Backbones, Fundamenta Informaticae, v.73 n.1,2, p.191-202, April 2006
	Adalbert Golomety , Alina Pitic , Iulia Golomety , Antoniu Pitic, Production planning by shuffle operation, Proceedings of the 11th WSEAS International Conference on Computers, p.178-183, July 26-28, 2007, Agios Nikolaos, Crete Island, Greece
	Adalbert Golomety , Alina Pitic , Iulia Golomety , Antoniu Pitic, Shuffle from sequential to parallel in production planning, WSEAS Transactions on Computer Research, v.3 n.1, p.1-8, January 2008
	Maurice H. ter Beek , Jetty Kleijn, Associativity of Infinite Synchronized Shuffles and Team Automata, Fundamenta Informaticae, v.91 n.3-4, p.437-461, August 2009