{"entities":{"Q1306565":{"pageid":1317315,"ns":120,"title":"Item:Q1306565","lastrevid":67120719,"modified":"2026-04-12T15:26:30Z","type":"item","id":"Q1306565","labels":{"en":{"language":"en","value":"Comparing expressibility of normed BPA and normed BPP processes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1347426"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$0AF321A7-1604-4403-9D6A-B0E3E0CBA7F9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c493a31cff9ee3c209fa19b37593e9027d62dfeb","datavalue":{"value":{"text":"Comparing expressibility of normed BPA and normed BPP processes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306565$2BAD1F44-BA3E-49F3-873F-244D03116929","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39fcf35ef29d30cb4d70b9fb6e1bc7757ca2a000","datavalue":{"value":"0947.68109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306565$15E84FB0-AFF2-42E3-97E3-26149D16E302","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"49f82df4d18eab422e11b74b412720f50f68da1a","datavalue":{"value":{"entity-type":"item","numeric-id":1306564,"id":"Q1306564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$EF7F3190-27E0-4937-A086-3304B03FFA6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e86fa9d0b9effd06fb644383c19d6a5b9829621e","datavalue":{"value":{"entity-type":"item","numeric-id":1006888,"id":"Q1006888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$B34687CA-49DB-41C9-A007-753B17F0AD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3e518c334d462c26c60c459e716d0942607e70d","datavalue":{"value":{"entity-type":"item","numeric-id":235697,"id":"Q235697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$F51E11DF-1F90-4BF8-BFAE-E5BA7975E21F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$79079CFE-DE79-4DFC-8C2B-58BF694F32A4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"17efae152c5b59503115bb21d795e62311ef5a22","datavalue":{"value":{"time":"+1999-11-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306565$5C7870C4-9768-4B59-98A3-2D68CB6F4FC7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6889c5bcdf397ccf496d75c44b6144333e640a87","datavalue":{"value":"We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \\(\\text{BPA}_\\tau\\) and normed \\(\\text{BPP}_\\tau\\) processes. We give such a characterization for the subclasses of normed BPA and normed BPP processes as well.   Next, we demonstrate the decidability of the problem whether for a given normed \\(\\text{BPA}_\\tau\\) process \\(\\Delta\\) there is some unspecified normed \\(\\text{BPP}_\\tau\\) process \\(\\Delta'\\) such that \\(\\Delta\\) and \\(\\Delta'\\) are bisimilar. The algorithm is polynomial. Furthermore, we show that if the answer to the previous question is positive, then (an example of) the process \\(\\Delta'\\) is effectively constructible. Analogous algorithms are provided for normed \\(\\text{BPP}_\\tau\\) processes. Simplified versions of the mentioned algorithms which work for normed BPA and normed BPP are given, too. As a simple consequence we obtain the decidability of bisimilarity in the union of normed \\(\\text{BPA}_\\tau\\) and normed \\(\\text{BPP}_\\tau\\) processes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306565$9714C90A-21E6-4CEC-9EF2-E60587721443","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306565$E7A0E6E3-0971-4C5F-941E-BC04AE2AA190","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"635834aa80ec034fbc624573a782ce868292d52b","datavalue":{"value":"1347426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306565$D2A7E226-7A6E-4D72-AD6E-F4C27A4063D4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d9c2e1f00facc619242af9af43a4aae006f38ad","datavalue":{"value":"transition systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306565$B1B04A7D-E123-4BAB-85C1-DC87E32C1CDA","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306565$08254496-C7C1-4FE0-A4E7-42FE46DF90B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"439f213c24ba041de21ecf7df085e8909b47724d","datavalue":{"value":"https://doi.org/10.1007/s002360050159","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306565$AF161C82-B978-4046-9D3E-239C3115BDFC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d62c40254e4c43d24912588701dbda16e14621be","datavalue":{"value":"W2059660155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306565$1AC26DCC-EB78-4CD6-895C-5878D29B74D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd96c579d2828d740feeb46b50f3d1693a2b18b2","datavalue":{"value":"10.1007/S002360050159","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306565$4D65F5C6-C714-44B8-A3D3-5F528204E0E4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82408f3441d796ed2cd7637698c16002dafde811","datavalue":{"value":{"entity-type":"item","numeric-id":4222869,"id":"Q4222869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3786c1119bed3ceef98eee7680a0a1ededcabc6e","datavalue":{"value":{"amount":"+0.9346464276313782","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306565$44C5FF93-AE44-4021-9909-725D3F7D674D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a69ecbcf836548863b623cfd4b9238e80a71836","datavalue":{"value":{"entity-type":"item","numeric-id":3541036,"id":"Q3541036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a82e304cec5fa0e00e32d249c026dc14a6816e3d","datavalue":{"value":{"amount":"+0.8935779929161072","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306565$ED94D794-79E5-4042-A158-F11A8EEE5CA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8d200a2dac8e851aa1f1862c4e1f2194c864e9f","datavalue":{"value":{"entity-type":"item","numeric-id":1959482,"id":"Q1959482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b81f02686691bd06db2b25117617df085fd2ca6a","datavalue":{"value":{"amount":"+0.8747678399085999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306565$5D0787BC-4D1B-483E-9BE7-14C77CFA9B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"730e7aac224263e971b91a763036d185e1229629","datavalue":{"value":{"entity-type":"item","numeric-id":5900564,"id":"Q5900564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2b0309ddf24b922836c8823b2a92a20636a8f7","datavalue":{"value":{"amount":"+0.8599507212638855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306565$578A01F2-EE52-432C-938E-83850E56FFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1396d1e0e17f6387e96f18e799337976c630069c","datavalue":{"value":{"entity-type":"item","numeric-id":4635801,"id":"Q4635801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3ca5d1862d2f077999276d484dc6779317654fa","datavalue":{"value":{"amount":"+0.827197790145874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1306565$EC25E071-3543-4C5F-8A41-FF22E45715B0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Comparing expressibility of normed BPA and normed BPP processes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Comparing_expressibility_of_normed_BPA_and_normed_BPP_processes"}}}}}