{"entities":{"Q1959657":{"pageid":1970399,"ns":120,"title":"Item:Q1959657","lastrevid":51098462,"modified":"2026-01-16T16:05:41Z","type":"item","id":"Q1959657","labels":{"en":{"language":"en","value":"Recognition of directed acyclic graphs by spanning tree automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5796909"}},"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":"Q1959657$35DF92E7-C69C-47C2-A853-ADEC0DDF3DE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"181d55ac8c595150721b668ed16993202c77dd12","datavalue":{"value":{"text":"Recognition of directed acyclic graphs by spanning tree automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1959657$638B87C6-ACDB-468B-BF7A-38313AA86496","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"be0aacc9dbc4a0308061943640def9643b0e1629","datavalue":{"value":"1207.68185","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$5E6FADEA-95B2-478F-9616-97C7BDE80E2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ec88d9498dd49efc548b5bf2d8fedace2c90433","datavalue":{"value":{"entity-type":"item","numeric-id":626921,"id":"Q626921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$309ADDE2-3920-4CD5-B42C-2F9E2A103A52","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":"Q1959657$330F7002-3DB5-4A01-8F58-FA3166D18CA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ecd011827033d53f67ff93e5fac32ebe2bf4df3d","datavalue":{"value":{"time":"+2010-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1959657$5E43FE16-1F30-4EF9-9301-0FE38A3D481E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$AE756907-75F9-42F0-A04C-C9C843DDACC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$91CCE167-D938-4ECC-8CEA-FDB4860D80FE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f77b2d45470d14bd8faad82c68e9351b98194478","datavalue":{"value":"5796909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$517299E0-4716-4EE5-8A84-7307542B140C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a84ba88a223d66a255cf717873de1a17d0ae80a1","datavalue":{"value":"tree automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$EC45CC4C-4EB2-42C2-A4EB-FD3D5C66F696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b30413bdc80736aeecdc7f80229ac89c0446304","datavalue":{"value":"directed acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$1E4B5FF9-DBF2-457E-8D9A-485AE8B3E780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$BB49E8E5-E1E9-4CE6-82ED-C74CF6326F95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$600E2727-E585-449C-8CA0-8CB2D6F6F3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb191028560f8580185d25fb1e0694b4ee05dbf4","datavalue":{"value":"series-parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$5910914F-3DED-41C3-96D7-51DB4F03D2EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30ea72a38f64e6859d89960e4cbd282e0ed54157","datavalue":{"value":"generalized series-parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1959657$0816F526-FB64-4747-B8D2-0A8BCB1FC737","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":"Q1959657$012A3F0D-878C-4C1F-A074-8D4160FB9514","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"240d44f5cedf89305693a4750bcd01085ae59821","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.06.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1959657$D07DA696-880F-42EF-AD36-736E43FEE98E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17d94cad6566851916b4ad7338253de834fb98af","datavalue":{"value":"W2038955206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$C0D2C243-2006-4B01-BDD8-EB5743050ED2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4565de18ad512dcc354f90d79d4edf03edab572d","datavalue":{"value":{"entity-type":"item","numeric-id":3637347,"id":"Q3637347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$31CAC5B4-B090-48DF-95AC-C41B65139B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6392c5dc99df0a72446467c8792ac270bf4b277a","datavalue":{"value":{"entity-type":"item","numeric-id":1041757,"id":"Q1041757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$C7ED4EB4-B024-450A-86D4-2840B37FB5E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c0396a221fb672ed5420003bc74eb6111e17537","datavalue":{"value":{"entity-type":"item","numeric-id":860863,"id":"Q860863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$43078DED-336C-4011-B9CB-2726DCB60DF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed018dd54b46de0c07fad418719f7f89a057758f","datavalue":{"value":{"entity-type":"item","numeric-id":5505521,"id":"Q5505521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$8F605633-42AE-4D15-BDF2-A63FED3639A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$6E8145C8-317B-4484-8CAB-1C5CE1FCC129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e6f48016104df1992910800e8df7fcd2533df48","datavalue":{"value":{"entity-type":"item","numeric-id":1336626,"id":"Q1336626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$D31E67D1-82B8-480E-8F17-17AA9DBC25B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57515aea1ad564d767f2a1d2b4fdb04b8bf50ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1274912,"id":"Q1274912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$C41A251D-5A0A-4567-A1C5-3102B6ACECBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f8a4ef0d6fda29423f4482c1d4637971076e668","datavalue":{"value":{"entity-type":"item","numeric-id":5897671,"id":"Q5897671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1959657$1A59B084-E20A-4124-8602-04C306B8159B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65c362eba71db15ed96b96d8faab8257cd5ee487","datavalue":{"value":"10.1016/J.TCS.2010.06.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1959657$28EEB242-7B98-4E2D-94A2-D7968605FF0B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f0215bebdfa3edeb8afc40d6af6697c694a16c2","datavalue":{"value":{"entity-type":"item","numeric-id":3637347,"id":"Q3637347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95b574686e2c607b1cf98af94e4b710bd25d248e","datavalue":{"value":{"amount":"+0.9830846190452576","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":"Q1959657$C4A54C4E-41FF-4FC8-A08A-26D0847D0F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d8e691ae5bd73efeefd3f20cc827e87fac50c65","datavalue":{"value":{"entity-type":"item","numeric-id":3192264,"id":"Q3192264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d082d5d699d022c155ce2c7e3acf411246413989","datavalue":{"value":{"amount":"+0.8710082769393921","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":"Q1959657$CCB33D77-8B01-48AB-B291-E771B9AD133D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b661b90d6816d357ffd6eeca983ecd4e5098a04","datavalue":{"value":{"entity-type":"item","numeric-id":5428246,"id":"Q5428246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9376e91d3d9c7c756ccb04acd8be9f8a7a9e71a1","datavalue":{"value":{"amount":"+0.7831102013587952","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":"Q1959657$801B27C9-232A-446A-9A14-8FF7EB87CE32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbbd31d95efd1301ebd8d4db8c8fad4437e4240e","datavalue":{"value":{"entity-type":"item","numeric-id":2798739,"id":"Q2798739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fb61952d125d88d81dbdef413b25baa8eb2eace","datavalue":{"value":{"amount":"+0.7817472219467163","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":"Q1959657$AADCCB6A-AFFA-4812-8933-AB435489AD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32c12a0f2bfcce9489ca3c8f1b67253bc91a8b5a","datavalue":{"value":{"entity-type":"item","numeric-id":1041757,"id":"Q1041757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8ba06b97d4b8f0b62352903e3ec6ab2b70fac4","datavalue":{"value":{"amount":"+0.7733312845230103","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":"Q1959657$1BF92311-CDCE-4992-8834-E0799C8BFF45","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1959657","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1959657"}}}}}