{"entities":{"Q5216306":{"pageid":7245876,"ns":120,"title":"Item:Q5216306","lastrevid":94477793,"modified":"2026-06-05T06:55:14Z","type":"item","id":"Q5216306","labels":{"en":{"language":"en","value":"Minimization of visibly pushdown automata is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7168150"}},"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":"Q5216306$24965F22-65DE-4F70-A048-19964B99A81B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf466b6e29604a42a28739871681b452f68bd37c","datavalue":{"value":{"entity-type":"item","numeric-id":553308,"id":"Q553308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$512FE3D7-BBCF-4BC4-A081-BA0546F21B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5a53865c1f184b73cba92d65c57544179b9e023","datavalue":{"value":{"entity-type":"item","numeric-id":407517,"id":"Q407517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$759759CD-5C73-462B-8187-DBC33A9BCC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bb93bd3091dc826856534537228702a0870e562","datavalue":{"value":{"entity-type":"item","numeric-id":2039965,"id":"Q2039965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$2B714ACF-1173-4F58-BA40-E65CAC343CE9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a7c9d6c0100675744974eb3bd7cd696e575460ae","datavalue":{"value":{"time":"+2020-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5216306$E2C1B248-3A70-4776-B39B-92CD31C9BBF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"314d78fa23af339265398e7c128423fbe25900da","datavalue":{"value":"https://arxiv.org/abs/1907.09563","type":"string"},"datatype":"url"},"type":"statement","id":"Q5216306$9668B911-7D3F-42A9-B139-52515798A840","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5216306$91525264-ADF3-4822-8FE2-866B74D7C3D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"62a49b155c9af634e6c3562b1547da1f7c08791a","datavalue":{"value":"68-XX","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5216306$E61AC670-4E10-483C-8145-8CA2485F7DDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f8871d08b2468b7706a3860188f2d4ec92a9e15b","datavalue":{"value":"7168150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5216306$DA12C5D1-D85E-4043-AA38-4462ADA0421D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba51c122061becbfe0e372cd8e7ac957a19e72e0","datavalue":{"value":"visibly pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q5216306$0FC353F4-8C48-4661-BBC6-6F4F2EC94C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a1279221fe7735b1b47afd1411b335eca7e3f0e","datavalue":{"value":"minimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5216306$B863B8F1-B72F-4B4A-A581-3C1EEF552828","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":"Q5216306$C6BD3CCF-8A0D-4810-8B60-46FD4103C188","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f81063e0001135f36876aa04e7b3df8c47842cd1","datavalue":{"value":{"entity-type":"item","numeric-id":5716856,"id":"Q5716856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$7E72588B-18F3-4973-ABBD-695D2E8890B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7aeeecf2d28d1d75570eca357b2bf733654064","datavalue":{"value":{"entity-type":"item","numeric-id":3580970,"id":"Q3580970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$A5BA0442-EE7D-42AD-8FD4-FA6E0BE8DCA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90ea3bb9e6afed09da0fd153369fbbb5dbd05ce","datavalue":{"value":{"entity-type":"item","numeric-id":414869,"id":"Q414869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$345895BE-6355-456F-A533-484EE1D4EE86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f79f3cf6637920f48119d2a9c0de92a2c28917","datavalue":{"value":{"entity-type":"item","numeric-id":3525563,"id":"Q3525563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$B88868B5-AD3A-4833-83D5-3CAD63F07FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$C650D464-FE42-4BF6-B072-EC03BA2EDDBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fac6ad175a4350089f5058cf57b56bddffbf8e9","datavalue":{"value":{"entity-type":"item","numeric-id":3303909,"id":"Q3303909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$34412550-6152-4D95-8B21-E7B19AC978E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23227ff9aa4dd1ea34046d3e4564bf94ef23f8d","datavalue":{"value":{"entity-type":"item","numeric-id":5756620,"id":"Q5756620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$F9511616-1874-4238-8FD1-CA8E5801411E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd79a1de38c165d0ca1355e68556bf899b647fc7","datavalue":{"value":{"entity-type":"item","numeric-id":703578,"id":"Q703578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$E46CB084-6635-4180-9A6F-4292E3874447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53026eff20cf878e72e195ddde23952c6fed9319","datavalue":{"value":{"entity-type":"item","numeric-id":882435,"id":"Q882435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$F74B5377-87D1-4302-9588-CA2C32780BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4e7f03e0bfff061db9847c399a80056bc6c3929","datavalue":{"value":{"entity-type":"item","numeric-id":3890112,"id":"Q3890112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5216306$E0631E10-56D1-4659-86D2-52D8D2096D0C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37f69ca181b7776d015bb6a6f782ec9ef43408a7","datavalue":{"value":{"entity-type":"item","numeric-id":3525563,"id":"Q3525563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce43bca1e6434d89dae2481c5c60716814bccb05","datavalue":{"value":{"amount":"+0.8330908417701721","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":"Q5216306$C96A3CEA-A93E-45E3-AE2E-42286AB43637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18ae7c485cf10bde4413132fce98d3ea1cbd5256","datavalue":{"value":{"entity-type":"item","numeric-id":3303909,"id":"Q3303909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acee4cf6ee298edc9d57b427baded8fee9e5bf17","datavalue":{"value":{"amount":"+0.8022726774215698","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":"Q5216306$91F1955C-C29B-4851-B369-1C0B6C3C199D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"048183140c44732c3eaed0a207c927f65c9c6b56","datavalue":{"value":{"entity-type":"item","numeric-id":3520301,"id":"Q3520301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2ecbd8cd1397f48878664c246b56d720e5e2eed","datavalue":{"value":{"amount":"+0.7780137658119202","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":"Q5216306$FEBF3F75-12B1-4973-99F7-E2CFDEE743C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd8db175580a73f7413caf19d8d8cc8684f7928a","datavalue":{"value":{"entity-type":"item","numeric-id":3623014,"id":"Q3623014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc2e0642e97a5ca7a7d90c73b6ebdb8077ec68c3","datavalue":{"value":{"amount":"+0.7745103240013123","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":"Q5216306$0288BA83-7230-44FB-9E2A-73D6D114CF17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2627c11505e99948132536f4ab41a29844be5439","datavalue":{"value":{"entity-type":"item","numeric-id":703578,"id":"Q703578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"174ba2d7a6efa4463e2b8c370086a2616da4014e","datavalue":{"value":{"amount":"+0.7726406455039978","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":"Q5216306$9E34F8D3-5771-471D-84C4-B34E3729746E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimization of visibly pushdown automata is NP-complete","badges":[]}}}}}