Access Restriction

Author Gischer, Jay
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Context-sensitive ♦ Regular languages ♦ Vector machine ♦ Shuffle languages ♦ Petri net
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.
Description Affiliation: Univ. of Washington, Seattle (Gischer, Jay)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 24
Issue Number 9
Page Count 9
Starting Page 597
Ending Page 605

Open content in new tab

   Open content in new tab
Source: ACM Digital Library