{"entities":{"Q4639894":{"pageid":6669475,"ns":120,"title":"Item:Q4639894","lastrevid":53081729,"modified":"2026-01-24T04:42:20Z","type":"item","id":"Q4639894","labels":{"en":{"language":"en","value":"Emptiness of ordered multi-pushdown automata is 2ETIME-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6868311"}},"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":"Q4639894$4F8286C5-C086-4C0E-97B9-CFEEF13653E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d482ab3545166ae4d8743a1b54d8e4af446d6720","datavalue":{"value":{"text":"Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4639894$B992C4B1-1715-4ABC-BBD3-5D9B6648D224","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"21648c89cdefd427a6fcf73ba839ea9977d08bb3","datavalue":{"value":"1387.68129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$1DD460A5-C819-4561-A5ED-EA3550BDACE2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c3c5c152d46a7b916686659906691e47328b6eb5","datavalue":{"value":"10.1142/S0129054117500332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$43D75E61-9773-4F16-9A43-E04BA078FFAB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"de80e021db34435e21a6613c8105f91a5d942b85","datavalue":{"value":{"entity-type":"item","numeric-id":479840,"id":"Q479840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$E9B6A940-D459-4064-837C-CD2CBC35CF8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"65221e215393442395d12a6532e173c4dee8b90f","datavalue":{"value":{"entity-type":"item","numeric-id":420854,"id":"Q420854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$D196A9A3-DEBA-4EFB-AD2A-2B1FC33940B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"48768ae81aa5edcb5110bd8b53b5885bdbc25ee1","datavalue":{"value":{"entity-type":"item","numeric-id":515662,"id":"Q515662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$3E1E6780-B0D8-469E-B00E-1D194410345A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"47adaa7123c6f3744cf7fa8eab088d52b4982295","datavalue":{"value":{"entity-type":"item","numeric-id":2703009,"id":"Q2703009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$4E6D3B6C-42D7-420F-9413-1842833AF794","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d4699b0c285cc0543fb8926c8b77482ad5d3e927","datavalue":{"value":{"time":"+2018-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4639894$665DB5CE-EC93-448A-A8FC-F67538F977F9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$FAF0EE4A-A65E-4647-A6D5-544E4BEAADA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$ECA909CE-0D00-4A41-8D0D-7E0D6AD4D66A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$6C86AFDD-7F5A-4B06-87DC-7C2B78178E77","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8bf5d626935bfc1799ca3b516aff3b0fd12858ad","datavalue":{"value":"6868311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$23B230EE-9C29-435C-9A5E-7CF9750120CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7c88f566c49426bb57067a5a1bea18c938c730c","datavalue":{"value":"multi-pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q4639894$65976882-C955-4FC5-9830-5455A6917DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9159d4f959d21ef7c3c5f2d36ede4144c26f9c","datavalue":{"value":"emptiness problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4639894$6C939F63-62B7-4D3F-AE4F-DEBB59654574","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":"Q4639894$D5EAB0B6-C7E6-44B5-8B47-1FC5CA6513F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aafe152d225aa7fd22548124305235260731e8ad","datavalue":{"value":{"entity-type":"item","numeric-id":3452213,"id":"Q3452213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$03DFD3F7-D615-446A-8494-E98A2B338EE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e3c2533ea5ed084d478562549cc3afbc206c903","datavalue":{"value":{"entity-type":"item","numeric-id":3584925,"id":"Q3584925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$6EA9A02C-AB2B-4299-8E81-321B2ACBD0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1798a40b142fd29eaea896aff9a22a0ad2a71c5a","datavalue":{"value":{"entity-type":"item","numeric-id":2908851,"id":"Q2908851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$CD57941E-C873-4C64-9A17-92C6184F0A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd11e93c75529377db826ac87ba05a72812a48a5","datavalue":{"value":{"entity-type":"item","numeric-id":3533004,"id":"Q3533004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$AA5867BF-1835-4402-8A73-2315E4B13308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"348807bc3eeb1ef3f0960854f7e42e0f63ffd940","datavalue":{"value":{"entity-type":"item","numeric-id":4649294,"id":"Q4649294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$A6929503-51AB-4A09-AFC1-CB9EFB5B68F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2af9edc2e188b2528c561e74501862b46f7ed766","datavalue":{"value":{"entity-type":"item","numeric-id":5247176,"id":"Q5247176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$C6B6BAA2-6677-4660-AD72-19A616B1C885","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e7a108370169c16838733bc613c6abdf38f709","datavalue":{"value":{"entity-type":"item","numeric-id":6044114,"id":"Q6044114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$7E692E12-3F3C-47E8-A9BE-DF25F10382E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74374a8fe3637c3aa0bd4d13c222f64d3f91ffd4","datavalue":{"value":{"entity-type":"item","numeric-id":5687660,"id":"Q5687660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$D717DCC4-4475-4F47-919D-EC1A3CEBFBB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a0489ecf14ddd62bb943fcc87a7de1bc35bdfb0","datavalue":{"value":{"entity-type":"item","numeric-id":344793,"id":"Q344793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$C6F5BD9C-14D3-4D83-A877-E0628CBC05B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$FE358F14-A116-4CE0-A9F7-553B8B76A2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a61f94f34b177df76a317c8d62663291a02395c","datavalue":{"value":{"entity-type":"item","numeric-id":4353558,"id":"Q4353558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$77E30ECE-3B8D-431C-9917-D34DE5E8D8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"664c83bf274f93d861a5c0c6834d01ddb129bcbf","datavalue":{"value":{"entity-type":"item","numeric-id":2912701,"id":"Q2912701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$B4B2F0E9-70C9-43DC-B948-9E17411FB3DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b37a78c90c339f054eefdad434a464e87238fe7b","datavalue":{"value":{"entity-type":"item","numeric-id":1183602,"id":"Q1183602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$425CD8FE-61DC-4EAE-8A20-2E9B19D852A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c6905418d13acee63d1d7cf97dfabef840c0ce1","datavalue":{"value":{"entity-type":"item","numeric-id":2922031,"id":"Q2922031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$F5C0356E-4336-4FC8-A599-8B2590974D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cb85b86517e33688ea4f1a6a764bb6dca96c127","datavalue":{"value":{"entity-type":"item","numeric-id":5890814,"id":"Q5890814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$41326989-5CCF-4550-8C05-6A0A9FC498F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728714e704897dc5089dad7a6353e4ee7c8d2097","datavalue":{"value":{"entity-type":"item","numeric-id":5458333,"id":"Q5458333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$E5B612C5-9BB1-46E5-9DE9-706A9D82EC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c5cea71c6aacfcb4cc8bc4d70a2c543dbb0d272","datavalue":{"value":{"entity-type":"item","numeric-id":5408550,"id":"Q5408550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$C8678D8B-077C-442B-AC1E-2125D2B349DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06a1669ea55c70484627fcb886923a0a7a7abbca","datavalue":{"value":{"entity-type":"item","numeric-id":5703798,"id":"Q5703798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$C16224EE-765B-453A-8577-C88F52E6DBC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1d994db7c4e27dfd9c5271d26b11f2863b4eccb","datavalue":{"value":{"entity-type":"item","numeric-id":810005,"id":"Q810005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$38C53ECA-62C1-44C4-BAFE-851467BDEEA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"771dc4fa97eb6e1f23c076ebcef18d48c08c990a","datavalue":{"value":{"entity-type":"item","numeric-id":3605543,"id":"Q3605543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$657B8AA1-A66C-43E9-BAE9-361FA3ADB3A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b3d28acd643d396b152fcaf01bfc8613dfbfd42","datavalue":{"value":{"entity-type":"item","numeric-id":5458334,"id":"Q5458334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$396032E3-C64D-4D0B-84CC-DEFF21292DCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d29e8c2e5f8ff005472e1895d79eed2b11560cb","datavalue":{"value":{"entity-type":"item","numeric-id":3540169,"id":"Q3540169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$E19E50C1-0AA8-4CCD-BAB9-1EF365755D27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21421521ce0dc9c3e052bb8dc5b74ac8dd2e20e5","datavalue":{"value":{"entity-type":"item","numeric-id":3090831,"id":"Q3090831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$A971A568-37C6-4045-86E6-A90460EC91B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b46ee26306d9882cb971bbc0a9173751fb67d0f","datavalue":{"value":{"entity-type":"item","numeric-id":2915173,"id":"Q2915173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$BAE0E2B5-33AD-4180-B09D-42688E29365C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c23415e046078c6c12f71e66b4ffe401fb291c65","datavalue":{"value":{"entity-type":"item","numeric-id":2957490,"id":"Q2957490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4639894$D75A0C1A-E015-4EFC-8E9A-94C4115B7CD6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4540e5cd793c340bd8e0d17c462278922a1efa17","datavalue":{"value":"https://doi.org/10.1142/s0129054117500332","type":"string"},"datatype":"url"},"type":"statement","id":"Q4639894$59B702ED-B79B-4201-A544-418598E0A466","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1557f2980dfab6a4d32a01e1e329008a881e580a","datavalue":{"value":"W2788350744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4639894$376C0450-C650-4544-B64F-447C1A28BC17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6e086ee94efccb580736131cc52997bf470995e","datavalue":{"value":{"entity-type":"item","numeric-id":3533004,"id":"Q3533004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd06b648ad7c5381221303079c11267d83036fa4","datavalue":{"value":{"amount":"+0.9455037713050842","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":"Q4639894$DB0F2003-8ADA-42DD-8B76-842DC6F0FFC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcedaa5216d1ed7592272401a8645a728dd14c56","datavalue":{"value":{"entity-type":"item","numeric-id":2914241,"id":"Q2914241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8ca2baf588b393d05eb2fa97b4798362a1334b5","datavalue":{"value":{"amount":"+0.8559868931770325","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":"Q4639894$3851FEF1-DE5B-463D-A245-EABD65F777B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"163e4fcefce5cb1a63667a3ef22d84884831c8ef","datavalue":{"value":{"entity-type":"item","numeric-id":2908851,"id":"Q2908851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b7594fe7a829ddfb3df37fa4a2fdd5fc9b94239","datavalue":{"value":{"amount":"+0.7843958139419556","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":"Q4639894$78F0B054-6C72-4279-986E-777F9FF7B121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"38ec2dda762e159abbf04e8dfe99592aa1bee5ad","datavalue":{"value":{"entity-type":"item","numeric-id":344793,"id":"Q344793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"901d2b3c704fe1d63df20db59116768ea5a7db3e","datavalue":{"value":{"amount":"+0.7805248498916626","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":"Q4639894$222279B5-EC19-43E9-93EF-0D1F7243E7C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bd58365ff924abe2050aad823458160c20d160e","datavalue":{"value":{"entity-type":"item","numeric-id":3584925,"id":"Q3584925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad2126efc6dad4464d782d1c42238612432a3078","datavalue":{"value":{"amount":"+0.7768168449401855","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":"Q4639894$243B17C3-488A-4CB3-9625-644FB543381A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4639894","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4639894"}}}}}