Shuffle languages, Petri nets, and context-sensitive grammars
The work
| Authors | Jay Loren Gischer |
|---|---|
| Editors | |
| Type | article |
| Year | 1981 |
| Citekey | gischer1981shuffle |
Where it appeared
| Published in | Communications of the ACM |
|---|---|
| Publisher | Association for Computing Machinery |
| Volume | 24 |
| Issue | 9 |
| Pages | 597--605 |
Identifiers
| DOI | 10.1145/358746.358767 |
|---|---|
| OpenAlex | W1965308680 |
Access
| Landing page | https://doi.org/10.1145/358746.358767 |
|---|---|
| Free full text | https://dl.acm.org/doi/pdf/10.1145/358746.358767 |
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
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.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-26 20:13 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{gischer1981shuffle,
title = {Shuffle languages, Petri nets, and context-sensitive grammars},
author = {Jay Loren Gischer},
year = {1981},
journal = {Communications of the ACM},
publisher = {Association for Computing Machinery},
volume = {24},
number = {9},
pages = {597--605},
doi = {10.1145/358746.358767},
}
This record lives at https://refs.drheap.org/gischer1981shuffle/ and will keep doing so.