Loading…
Beyond Language Equivalence on Visibly Pushdown Automata
We study (bi)simulation-like preorder/equivalence checking on the class of visibly pushdown automata and its natural subclasses visibly BPA (Basic Process Algebra) and visibly one-counter automata. We describe generic methods for proving complexity upper and lower bounds for a number of studied preo...
Saved in:
| Published in: | Logical methods in computer science 2009-01, Vol.5, Issue 1 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683 |
| container_end_page | |
| container_issue | |
| container_start_page | |
| container_title | Logical methods in computer science |
| container_volume | 5, Issue 1 |
| creator | Srba, Jiří |
| description | We study (bi)simulation-like preorder/equivalence checking on the class of
visibly pushdown automata and its natural subclasses visibly BPA (Basic Process
Algebra) and visibly one-counter automata. We describe generic methods for
proving complexity upper and lower bounds for a number of studied preorders and
equivalences like simulation, completed simulation, ready simulation, 2-nested
simulation preorders/equivalences and bisimulation equivalence. Our main
results are that all the mentioned equivalences and preorders are
EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly
one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for
visibly one-counter automata improves also the previously known DP-hardness
results for ordinary one-counter automata and one-counter nets. Finally, we
study regularity checking problems for visibly pushdown automata and show that
they can be decided in polynomial time. |
| doi_str_mv | 10.2168/LMCS-5(1:2)2009 |
| format | article |
| fullrecord | <record><control><sourceid>doaj_cross</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_1b1b72d13dc24b74bf32f2cd1a3254ba</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_1b1b72d13dc24b74bf32f2cd1a3254ba</doaj_id><sourcerecordid>oai_doaj_org_article_1b1b72d13dc24b74bf32f2cd1a3254ba</sourcerecordid><originalsourceid>FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683</originalsourceid><addsrcrecordid>eNpN0DtPwzAQwHELgURVOrNmhCE0d44dm61UPCoFgcRjtfwsqdIY8gD129NShLjlTjf8hj8hp5BdIHAxLe_nTyk7g0s8xyyTB2QEgmcpk0V--O8-JpOuW2XboRQE8hERV34TG5eUulkOeumT64-h-tS1b6xPYpO8Vl1l6k3yOHRvLn41yWzo41r3-oQcBV13fvK7x-Tl5vp5fpeWD7eL-axMLc1FnwbGsQDNPKPcFbkWgD5ILVkhMfMaJTIreRBGcuCGGsedCwh5oAhouaBjsti7LuqVem-rtW43KupK_Txiu1S67StbewUGTIEOqLOYmyI3WySgdaApstzorTXdW7aNXdf68OdBpnYd1a6jYgoUql1H-g3abmS5</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Beyond Language Equivalence on Visibly Pushdown Automata</title><source>EZB Electronic Journals Library</source><creator>Srba, Jiří</creator><creatorcontrib>Srba, Jiří</creatorcontrib><description>We study (bi)simulation-like preorder/equivalence checking on the class of
visibly pushdown automata and its natural subclasses visibly BPA (Basic Process
Algebra) and visibly one-counter automata. We describe generic methods for
proving complexity upper and lower bounds for a number of studied preorders and
equivalences like simulation, completed simulation, ready simulation, 2-nested
simulation preorders/equivalences and bisimulation equivalence. Our main
results are that all the mentioned equivalences and preorders are
EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly
one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for
visibly one-counter automata improves also the previously known DP-hardness
results for ordinary one-counter automata and one-counter nets. Finally, we
study regularity checking problems for visibly pushdown automata and show that
they can be decided in polynomial time.</description><identifier>ISSN: 1860-5974</identifier><identifier>EISSN: 1860-5974</identifier><identifier>DOI: 10.2168/LMCS-5(1:2)2009</identifier><language>eng</language><publisher>Logical Methods in Computer Science e.V</publisher><subject>computer science - computational complexity ; computer science - logic in computer science ; f.4.3</subject><ispartof>Logical methods in computer science, 2009-01, Vol.5, Issue 1</ispartof><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683</citedby><cites>FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27903,27904</link.rule.ids></links><search><creatorcontrib>Srba, Jiří</creatorcontrib><title>Beyond Language Equivalence on Visibly Pushdown Automata</title><title>Logical methods in computer science</title><description>We study (bi)simulation-like preorder/equivalence checking on the class of
visibly pushdown automata and its natural subclasses visibly BPA (Basic Process
Algebra) and visibly one-counter automata. We describe generic methods for
proving complexity upper and lower bounds for a number of studied preorders and
equivalences like simulation, completed simulation, ready simulation, 2-nested
simulation preorders/equivalences and bisimulation equivalence. Our main
results are that all the mentioned equivalences and preorders are
EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly
one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for
visibly one-counter automata improves also the previously known DP-hardness
results for ordinary one-counter automata and one-counter nets. Finally, we
study regularity checking problems for visibly pushdown automata and show that
they can be decided in polynomial time.</description><subject>computer science - computational complexity</subject><subject>computer science - logic in computer science</subject><subject>f.4.3</subject><issn>1860-5974</issn><issn>1860-5974</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2009</creationdate><recordtype>article</recordtype><sourceid>DOA</sourceid><recordid>eNpN0DtPwzAQwHELgURVOrNmhCE0d44dm61UPCoFgcRjtfwsqdIY8gD129NShLjlTjf8hj8hp5BdIHAxLe_nTyk7g0s8xyyTB2QEgmcpk0V--O8-JpOuW2XboRQE8hERV34TG5eUulkOeumT64-h-tS1b6xPYpO8Vl1l6k3yOHRvLn41yWzo41r3-oQcBV13fvK7x-Tl5vp5fpeWD7eL-axMLc1FnwbGsQDNPKPcFbkWgD5ILVkhMfMaJTIreRBGcuCGGsedCwh5oAhouaBjsti7LuqVem-rtW43KupK_Txiu1S67StbewUGTIEOqLOYmyI3WySgdaApstzorTXdW7aNXdf68OdBpnYd1a6jYgoUql1H-g3abmS5</recordid><startdate>20090126</startdate><enddate>20090126</enddate><creator>Srba, Jiří</creator><general>Logical Methods in Computer Science e.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>DOA</scope></search><sort><creationdate>20090126</creationdate><title>Beyond Language Equivalence on Visibly Pushdown Automata</title><author>Srba, Jiří</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2009</creationdate><topic>computer science - computational complexity</topic><topic>computer science - logic in computer science</topic><topic>f.4.3</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Srba, Jiří</creatorcontrib><collection>CrossRef</collection><collection>Directory of Open Access Journals</collection><jtitle>Logical methods in computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Srba, Jiří</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Beyond Language Equivalence on Visibly Pushdown Automata</atitle><jtitle>Logical methods in computer science</jtitle><date>2009-01-26</date><risdate>2009</risdate><volume>5, Issue 1</volume><issn>1860-5974</issn><eissn>1860-5974</eissn><abstract>We study (bi)simulation-like preorder/equivalence checking on the class of
visibly pushdown automata and its natural subclasses visibly BPA (Basic Process
Algebra) and visibly one-counter automata. We describe generic methods for
proving complexity upper and lower bounds for a number of studied preorders and
equivalences like simulation, completed simulation, ready simulation, 2-nested
simulation preorders/equivalences and bisimulation equivalence. Our main
results are that all the mentioned equivalences and preorders are
EXPTIME-complete on visibly pushdown automata, PSPACE-complete on visibly
one-counter automata and P-complete on visibly BPA. Our PSPACE lower bound for
visibly one-counter automata improves also the previously known DP-hardness
results for ordinary one-counter automata and one-counter nets. Finally, we
study regularity checking problems for visibly pushdown automata and show that
they can be decided in polynomial time.</abstract><pub>Logical Methods in Computer Science e.V</pub><doi>10.2168/LMCS-5(1:2)2009</doi><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 1860-5974 |
| ispartof | Logical methods in computer science, 2009-01, Vol.5, Issue 1 |
| issn | 1860-5974 1860-5974 |
| language | eng |
| recordid | cdi_doaj_primary_oai_doaj_org_article_1b1b72d13dc24b74bf32f2cd1a3254ba |
| source | EZB Electronic Journals Library |
| subjects | computer science - computational complexity computer science - logic in computer science f.4.3 |
| title | Beyond Language Equivalence on Visibly Pushdown Automata |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-24T22%3A54%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-doaj_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Beyond%20Language%20Equivalence%20on%20Visibly%20Pushdown%20Automata&rft.jtitle=Logical%20methods%20in%20computer%20science&rft.au=Srba,%20Ji%C5%99%C3%AD&rft.date=2009-01-26&rft.volume=5,%20Issue%201&rft.issn=1860-5974&rft.eissn=1860-5974&rft_id=info:doi/10.2168/LMCS-5(1:2)2009&rft_dat=%3Cdoaj_cross%3Eoai_doaj_org_article_1b1b72d13dc24b74bf32f2cd1a3254ba%3C/doaj_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c348t-f56271a5e536d74a812ef9a957920ea2925c96f8b9616b3bd6ddf214f3212c683%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true |