{"entities":{"Q801689":{"pageid":803537,"ns":120,"title":"Item:Q801689","lastrevid":64442577,"modified":"2026-04-11T19:53:48Z","type":"item","id":"Q801689","labels":{"en":{"language":"en","value":"An extended direct branching algorithm for checking equivalence of deterministic pushdown automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3880133"}},"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":"Q801689$9BEEE32B-6BCE-4DD0-BF2D-8E377CD9F761","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0a36dbdbb7c56c4c9760f411c3db91cf9bb3f104","datavalue":{"value":{"text":"An extended direct branching algorithm for checking equivalence of deterministic pushdown automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q801689$669A1DD9-05F1-4041-9EB7-B145C5828F59","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7f441de466c2bad28b4b49290aeb3d214a4bc29","datavalue":{"value":"0552.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$F4E23AC4-43A1-4922-B744-4CFD67068601","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0cacf5e617c668e79e15cf067c3861a32b8ea401","datavalue":{"value":"10.1016/0304-3975(84)90026-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$D89AE8F8-CA39-4F45-B479-5A382B5BCC30","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a88493808da78834a7ac0bf4a8a3155ab282fc3","datavalue":{"value":{"entity-type":"item","numeric-id":638533,"id":"Q638533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$326AFB84-0731-4A59-A213-062D8A99EDF4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$0F3D6118-5135-48B3-90BD-D77C6BB12A51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q801689$8DEB4468-B0B4-4ECB-82B6-5DBFCDBABB49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"375ad4e028537f558942b10be0aa4fb58258b781","datavalue":{"value":"This paper extends the author's direct branching algorithm [Inf. Control. 52, 187-238 (1982; Zbl 0541.68053)] for checking equivalence of deterministic pushdown automata. It does so by providing a technique called 'halting' for dealing with nodes with unbounded degree in the comparison tree. This may occur when a skipping step may be applied infinitely many times to a certain node, as a result of infinite sequences of \\(\\epsilon\\)-moves. This extension allows the algorithm to check equivalence of the deterministic pushdown automata when none of them is real-time, but in a certain condition that properly contains a case where one of them is real-time strict.","type":"string"},"datatype":"string"},"type":"statement","id":"Q801689$4E39CE20-7FD6-4D87-ACEB-B37DB97D58BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$A3102A5C-CC1E-43E4-A40E-EB49D21BF76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$950DC4CF-6C0A-4695-8DD5-62B824B747BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c032c1f200ff371073e8a0f37b9a76ad222e329","datavalue":{"value":"3880133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$CFA2BC29-70B6-4F89-AD71-C8EB22FDB84E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a946af12c2d32756db6185c59cea0cb15a6a334a","datavalue":{"value":"direct branching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q801689$EB04D358-F913-4ED9-87E5-453EA7A81504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbf6305de3a68ac44c03a27841c5eb30b478a947","datavalue":{"value":"equivalence of deterministic pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q801689$D4D31E19-E1AA-4D53-844E-77560381EDA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bff40ef96b083881ba9aac8bde6d0204c8902f58","datavalue":{"value":"comparison tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q801689$0C199D84-AED9-45DA-9026-231600F414A6","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":"Q801689$C640C7D1-AC0F-4C3E-96B1-7A18BB370C48","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"78c6ff13a578ab3d59b619dc7bfd47d8f585fb9d","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90026-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q801689$63611BE7-91C5-4735-9865-088EC7BCCF77","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e7289bc091fe727933d39714fe3306d09bc3855","datavalue":{"value":"W2059683551","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801689$55463647-C00D-4F25-9B89-B80F2B88F1D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"085f7af87c85d92c5774b1ac0ff37f2736cd97c1","datavalue":{"value":{"entity-type":"item","numeric-id":1239606,"id":"Q1239606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$D0C67A0E-6ABA-49C6-974C-40E9D49256DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d583fc00d1fe73786a69f9291791be750d1c45cd","datavalue":{"value":{"entity-type":"item","numeric-id":1246271,"id":"Q1246271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$FAB38115-6AC9-42CA-A474-C9088496AA15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e0b8f61d70bb48c00c21d61a4a73263d682547e","datavalue":{"value":{"entity-type":"item","numeric-id":1152220,"id":"Q1152220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$E6F19ACD-5051-4A48-91EF-A10993B79573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be27978c3a4bb100378019f7b702eaca9386491e","datavalue":{"value":{"entity-type":"item","numeric-id":3703289,"id":"Q3703289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$842FA9D9-8C98-4C49-B5B7-22B5DEEA6CA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0711f0bf590c2207dac6faa5788ef613584cd7d","datavalue":{"value":{"entity-type":"item","numeric-id":1132642,"id":"Q1132642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$406059C1-A69D-4311-B60A-DE142C8BCDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b921830a8302ea4fe8b72707f9af73a2a84913f","datavalue":{"value":{"entity-type":"item","numeric-id":3962488,"id":"Q3962488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$1978BAF1-019C-49E8-B369-CC2FA1B45583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bff8b19dadebd5e3dfb4db8cb0e80dde8d233cf7","datavalue":{"value":{"entity-type":"item","numeric-id":5684249,"id":"Q5684249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$5FABA33B-A46B-4E7B-A762-D35BC609E5E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"233d64506c1bbc043413c13cd64bb09b3ed4f887","datavalue":{"value":{"entity-type":"item","numeric-id":1259173,"id":"Q1259173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$83DBF263-B16E-47B3-95C1-4DF137FDDBD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78c0514e66cd471a92fa064dd5bb6cdadee1b293","datavalue":{"value":{"entity-type":"item","numeric-id":3923602,"id":"Q3923602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$95F93DB1-05D1-4F69-B039-20C0470C3599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422f13e0987f12a34d425454745bbbb66a566dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4072875,"id":"Q4072875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$9254A28D-9230-4028-B8F4-429E4EBA4E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec7365ae7ff2e7eb7ba57dcda7a377d50b921a5","datavalue":{"value":{"entity-type":"item","numeric-id":1254241,"id":"Q1254241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$4A19CDE9-F1D4-4B79-93BC-59964BC40B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebecac120edee416044dfc9fa2b60d66e0ccbe82","datavalue":{"value":{"entity-type":"item","numeric-id":1238431,"id":"Q1238431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$99D923A6-DFD1-47C0-A4E7-3C863CDA1CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df000af455f92229092d2f091c1587b6080cf496","datavalue":{"value":{"entity-type":"item","numeric-id":4174788,"id":"Q4174788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$0C0828DA-5780-488D-AE23-8A7ED9675A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d123ce3c6592eaecceee504819584bb2976aea7","datavalue":{"value":{"entity-type":"item","numeric-id":3888532,"id":"Q3888532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$DF52C6D3-C6E2-4C11-AA85-F57ACCF68E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7c303ddbf6a6d3cdfdfc57aa889b80b87656bfb","datavalue":{"value":{"entity-type":"item","numeric-id":3886866,"id":"Q3886866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$C69A8362-E0AE-4F2C-AB4B-F4FF0FE08EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f655404f5019528c0ff6f0cb07a94b157182d6db","datavalue":{"value":{"entity-type":"item","numeric-id":1158757,"id":"Q1158757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$C5E298F3-55D6-4B85-AD7A-17D4C66EB75D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e16d1dc4052e71d6b4ce452bdd1e1e49e7dff8b","datavalue":{"value":{"entity-type":"item","numeric-id":4144192,"id":"Q4144192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$96C578AA-E54D-4E13-9F9B-648F267C0532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b9d693ee9f84d5128fc7c86fda922f6bfcc20f5","datavalue":{"value":{"entity-type":"item","numeric-id":5609393,"id":"Q5609393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$60A679E5-A0BD-4568-B19E-AF68D6FC86DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61cb8280fa36fe466f451510204017197a7e8db6","datavalue":{"value":{"entity-type":"item","numeric-id":1230509,"id":"Q1230509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$F7D24091-B0A8-4A1C-8EE3-AFB58E80A6A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2dd8b739cacaef27ebd748b3d0d83c5cbbc73a","datavalue":{"value":{"entity-type":"item","numeric-id":3327736,"id":"Q3327736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$BA588D58-FFAE-4426-8465-6E9C45E7A260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c6d64280da704caa36d905dfda60b4db61057e2","datavalue":{"value":{"entity-type":"item","numeric-id":1838320,"id":"Q1838320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$BD9A7656-BE94-46E5-A408-E5D2AA58191C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88bf75d5fa4365193506074c05cd6ee2b649a0d9","datavalue":{"value":{"entity-type":"item","numeric-id":3951577,"id":"Q3951577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$9D0B503B-C2EC-447B-A979-FB58826E0405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef3dea0e266f78319fee7cbf7f7f4b7c1769f54","datavalue":{"value":{"entity-type":"item","numeric-id":3682403,"id":"Q3682403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$FACEC8A0-D34F-4DC9-98AA-6D9301C3036C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6c9ad1af6635d001f4350001772960e0e5560f","datavalue":{"value":{"entity-type":"item","numeric-id":4772713,"id":"Q4772713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$DB03FB4F-3775-43B6-A987-DDEC5A08B140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"202fa537549d862287e8c72112377f480beedfed","datavalue":{"value":{"entity-type":"item","numeric-id":1218272,"id":"Q1218272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$CBC7923D-F6B9-4228-A8CE-F6A32A898389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"953e42d0f1e941f940db5ab546e692041fe4bbbe","datavalue":{"value":{"entity-type":"item","numeric-id":4055220,"id":"Q4055220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$9AEDC671-40E2-4C74-8421-7EE7A0490E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d3ac622b328910e75936341b1e402c9a29a726b","datavalue":{"value":{"entity-type":"item","numeric-id":1165588,"id":"Q1165588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801689$C9B1AF94-E0EB-4FD0-8770-F66E9BF528BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b60d4915e05296216bc2e783adc07816ee14f3b","datavalue":{"value":{"entity-type":"item","numeric-id":2458041,"id":"Q2458041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3d2fadf78aea4862687a1433584c24564917956","datavalue":{"value":{"amount":"+0.7612870931625366","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":"Q801689$AA61F72D-A603-4714-83C6-4F5C0E43FD8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"389ecb0576ae1535eb6ddb56b4c799cee7b10be9","datavalue":{"value":{"entity-type":"item","numeric-id":3327736,"id":"Q3327736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a41e4a05f0ad6b2194a8be7bf241070a85ac286","datavalue":{"value":{"amount":"+0.7515827417373657","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":"Q801689$021B105C-DEB2-4132-AA2C-8F91F2EB4D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"426a6e5f7cffbaf4c8d63ce6ae4bf660a0afba49","datavalue":{"value":{"entity-type":"item","numeric-id":1124364,"id":"Q1124364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f098812fbb471ca52a91685987e1b521ee0d996","datavalue":{"value":{"amount":"+0.7454308867454529","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":"Q801689$37E7849E-C26F-47C7-88C6-756371A72427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f93994764c5550e37a603465d2e209a11d145bf","datavalue":{"value":{"entity-type":"item","numeric-id":1894681,"id":"Q1894681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5dcb653156a77d5609da0a2d06f098f9b68e176","datavalue":{"value":{"amount":"+0.7386548519134521","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":"Q801689$637F5C02-2178-4823-B1C8-54D5A028233E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e339e7b585026668beb26e95b634ac19810f508a","datavalue":{"value":{"entity-type":"item","numeric-id":5941060,"id":"Q5941060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3218a8f0e4a49f6ff42810fe9bdde8e545f7f7a7","datavalue":{"value":{"amount":"+0.734286367893219","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":"Q801689$618E0586-F155-4C5F-9D40-846C13276E32","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extended direct branching algorithm for checking equivalence of deterministic pushdown automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_extended_direct_branching_algorithm_for_checking_equivalence_of_deterministic_pushdown_automata"}}}}}