Pushdown automata, multiset automata, and Petri nets

In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpret...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001, Vol.256 (1), p.3-21
Main Authors: Hirshfeld, Yoram, Moller, Faron
Format: Article
Language:English
Subjects:
Automata
Bisimulation
Concurrency
Petri nets
Rewrite systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343
cites cdi_FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343
container_end_page 21
container_issue 1
container_start_page 3
container_title Theoretical computer science
container_volume 256
creator Hirshfeld, Yoram
Moller, Faron
description In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpreting concatenation as parallel composition. In this way, we provide natural definitions for commutative (parallel) context-free automata, multiset (parallel, or random access, pushdown) automata, and Petri nets. We provide example automata which demonstrate the strictness of this hierarchy. In particular, we provide a proof of an earlier conjecture by Moller: that multiset automata form a proper subset of Petri nets. This result contrasts with the result of Caucal for the analogous question in the sequential case where the hierarchy collapses.
doi_str_mv 10.1016/S0304-3975(00)00099-2
format article
fullrecord <record><control><sourceid>proquest_swepu</sourceid><recordid>TN_cdi_swepub_primary_oai_DiVA_org_uu_36508</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0304397500000992</els_id><sourcerecordid>26891550</sourcerecordid><originalsourceid>FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343</originalsourceid><addsrcrecordid>eNqFkNtKxDAQhoMouK4-gtArUbQ6ado0uZJlPcKCCx5uQ5qkGum2aw4uvr3drYh3Xs0w880P8yF0iOEcA6YXj0AgTwkvi2OAEwDgPM220Aizsm8ynm-j0S-yi_a8f-8hKEo6Qvk8-jfdrdpExtAtZJBnySI2wXoT_oxkq5O5Cc4mrQl-H-3UsvHm4KeO0fPN9dP0Lp093N5PJ7NU5RkOqVbAleE5BaWrAmuioQacM6WBE8C83yvGtJKyrijDiuKMSarqupQZqUhOxuh0yPUrs4yVWDq7kO5LdNKKK_syEZ17FTEKQgtgPX000EvXfUTjg1hYr0zTyNZ00YuMMo6LAnqwGEDlOu-dqX-DMYi1UbExKta6BIDYGBVZf3c53Jn-509rnPDKmlYZbZ1RQejO_pPwDQfKfXk</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>26891550</pqid></control><display><type>article</type><title>Pushdown automata, multiset automata, and Petri nets</title><source>ScienceDirect Journals</source><creator>Hirshfeld, Yoram ; Moller, Faron</creator><creatorcontrib>Hirshfeld, Yoram ; Moller, Faron</creatorcontrib><description>In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpreting concatenation as parallel composition. In this way, we provide natural definitions for commutative (parallel) context-free automata, multiset (parallel, or random access, pushdown) automata, and Petri nets. We provide example automata which demonstrate the strictness of this hierarchy. In particular, we provide a proof of an earlier conjecture by Moller: that multiset automata form a proper subset of Petri nets. This result contrasts with the result of Caucal for the analogous question in the sequential case where the hierarchy collapses.</description><identifier>ISSN: 0304-3975</identifier><identifier>EISSN: 1879-2294</identifier><identifier>DOI: 10.1016/S0304-3975(00)00099-2</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Automata ; Bisimulation ; Concurrency ; Petri nets ; Rewrite systems</subject><ispartof>Theoretical computer science, 2001, Vol.256 (1), p.3-21</ispartof><rights>2001 Elsevier Science B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343</citedby><cites>FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,4024,27923,27924,27925</link.rule.ids><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-36508$$DView record from Swedish Publication Index$$Hfree_for_read</backlink></links><search><creatorcontrib>Hirshfeld, Yoram</creatorcontrib><creatorcontrib>Moller, Faron</creatorcontrib><title>Pushdown automata, multiset automata, and Petri nets</title><title>Theoretical computer science</title><description>In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpreting concatenation as parallel composition. In this way, we provide natural definitions for commutative (parallel) context-free automata, multiset (parallel, or random access, pushdown) automata, and Petri nets. We provide example automata which demonstrate the strictness of this hierarchy. In particular, we provide a proof of an earlier conjecture by Moller: that multiset automata form a proper subset of Petri nets. This result contrasts with the result of Caucal for the analogous question in the sequential case where the hierarchy collapses.</description><subject>Automata</subject><subject>Bisimulation</subject><subject>Concurrency</subject><subject>Petri nets</subject><subject>Rewrite systems</subject><issn>0304-3975</issn><issn>1879-2294</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2001</creationdate><recordtype>article</recordtype><recordid>eNqFkNtKxDAQhoMouK4-gtArUbQ6ado0uZJlPcKCCx5uQ5qkGum2aw4uvr3drYh3Xs0w880P8yF0iOEcA6YXj0AgTwkvi2OAEwDgPM220Aizsm8ynm-j0S-yi_a8f-8hKEo6Qvk8-jfdrdpExtAtZJBnySI2wXoT_oxkq5O5Cc4mrQl-H-3UsvHm4KeO0fPN9dP0Lp093N5PJ7NU5RkOqVbAleE5BaWrAmuioQacM6WBE8C83yvGtJKyrijDiuKMSarqupQZqUhOxuh0yPUrs4yVWDq7kO5LdNKKK_syEZ17FTEKQgtgPX000EvXfUTjg1hYr0zTyNZ00YuMMo6LAnqwGEDlOu-dqX-DMYi1UbExKta6BIDYGBVZf3c53Jn-509rnPDKmlYZbZ1RQejO_pPwDQfKfXk</recordid><startdate>2001</startdate><enddate>2001</enddate><creator>Hirshfeld, Yoram</creator><creator>Moller, Faron</creator><general>Elsevier B.V</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>ADTPV</scope><scope>AOWAS</scope><scope>DF2</scope></search><sort><creationdate>2001</creationdate><title>Pushdown automata, multiset automata, and Petri nets</title><author>Hirshfeld, Yoram ; Moller, Faron</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2001</creationdate><topic>Automata</topic><topic>Bisimulation</topic><topic>Concurrency</topic><topic>Petri nets</topic><topic>Rewrite systems</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hirshfeld, Yoram</creatorcontrib><creatorcontrib>Moller, Faron</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>SwePub</collection><collection>SwePub Articles</collection><collection>SWEPUB Uppsala universitet</collection><jtitle>Theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hirshfeld, Yoram</au><au>Moller, Faron</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Pushdown automata, multiset automata, and Petri nets</atitle><jtitle>Theoretical computer science</jtitle><date>2001</date><risdate>2001</risdate><volume>256</volume><issue>1</issue><spage>3</spage><epage>21</epage><pages>3-21</pages><issn>0304-3975</issn><eissn>1879-2294</eissn><abstract>In this paper, we consider various classes of (infinite-state) automata generated by simple rewrite transition systems. These classes are defined by two natural hierarchies, one given by interpreting concatenation of symbols in the rewrite system as sequential composition, and the other by interpreting concatenation as parallel composition. In this way, we provide natural definitions for commutative (parallel) context-free automata, multiset (parallel, or random access, pushdown) automata, and Petri nets. We provide example automata which demonstrate the strictness of this hierarchy. In particular, we provide a proof of an earlier conjecture by Moller: that multiset automata form a proper subset of Petri nets. This result contrasts with the result of Caucal for the analogous question in the sequential case where the hierarchy collapses.</abstract><pub>Elsevier B.V</pub><doi>10.1016/S0304-3975(00)00099-2</doi><tpages>19</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0304-3975
ispartof Theoretical computer science, 2001, Vol.256 (1), p.3-21
issn 0304-3975
1879-2294
language eng
recordid cdi_swepub_primary_oai_DiVA_org_uu_36508
source ScienceDirect Journals
subjects Automata
Bisimulation
Concurrency
Petri nets
Rewrite systems
title Pushdown automata, multiset automata, and Petri nets
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T23%3A51%3A12IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_swepu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Pushdown%20automata,%20multiset%20automata,%20and%20Petri%20nets&rft.jtitle=Theoretical%20computer%20science&rft.au=Hirshfeld,%20Yoram&rft.date=2001&rft.volume=256&rft.issue=1&rft.spage=3&rft.epage=21&rft.pages=3-21&rft.issn=0304-3975&rft.eissn=1879-2294&rft_id=info:doi/10.1016/S0304-3975(00)00099-2&rft_dat=%3Cproquest_swepu%3E26891550%3C/proquest_swepu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c421t-dc09ce9460cdb51d3d0f0148cd093019dc0c88dcaafb681c6128a6cff7a23b343%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=26891550&rft_id=info:pmid/&rfr_iscdi=true