{"entities":{"Q1975208":{"pageid":1985950,"ns":120,"title":"Item:Q1975208","lastrevid":46902306,"modified":"2025-12-25T20:01:04Z","type":"item","id":"Q1975208","labels":{"en":{"language":"en","value":"Generalized definite set constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1428432"}},"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":"Q1975208$7EE6EE7C-6228-4B11-A8EA-C693E0D362B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f99275ecf6fc7f9f65aa80fe4a01c716eac7f726","datavalue":{"value":{"text":"Generalized definite set constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1975208$055AA5C1-7FF0-4128-9C41-CBABA8EDA650","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa246a0b57630f24d37ddbd56ceb33e26f53debe","datavalue":{"value":"0953.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$523122D3-4625-4462-AC20-43CA11D2D03A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"120c05fb58f786f0440cff36476ced50011452cd","datavalue":{"value":"10.1023/A:1009826603139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$C8F0C0D7-61F5-4FB4-B05E-87E11EDB746C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"173a37240a6b9d999a09f4b3d08a9c5c41e7cf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1607042,"id":"Q1607042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975208$94C43B2F-DB83-4181-8C4E-729DBC2F18BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2612fb8911c7209863c4cf5be1c1501e9eb3919e","datavalue":{"value":{"entity-type":"item","numeric-id":915430,"id":"Q915430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975208$029BF8AC-B8E8-4AA0-9EC8-700835CB722F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9725319a4d69c8b0f9e016d856caaf201d29cbe5","datavalue":{"value":{"entity-type":"item","numeric-id":462480,"id":"Q462480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975208$8B936451-3612-429B-8853-28B1EC518D3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a94d1d6f5ae333511fea1192115f95b08e9c8fb1","datavalue":{"value":{"entity-type":"item","numeric-id":202524,"id":"Q202524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975208$E8D4AA32-DB32-4F9D-B3BD-47A3AFA837E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d1d54670924db26a74d9a3b5e6224e9f60db0e3","datavalue":{"value":{"time":"+2001-01-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":"Q1975208$C1822D38-1FEE-420F-9535-C6059E787F6D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"abfc39fe1b1d498af13026c2421dd318bf038521","datavalue":{"value":"Building neatly on results of N. Heintze and J. Jaffar on a decision procedure for a class of Herbrand set constraints, the authors prove several interesting results on the computational complexity of set constraints. E.g., they present an algorithm which provides a DEXPTIME test for the satisfiability problem of shallow systems of generalized definite set constraints. The algorithm for the satisfiability problem is based on use of deterministic bottom-up tree automata.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975208$266C441F-F4F7-45D6-BD92-21BFF79753DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$40180165-EECA-4852-913A-F05E36553499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$42548FF0-54BF-46AC-A60C-2480F7AD161B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$DD18F45C-1675-4793-B825-DFDCF26C3617","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7bfb2d5c06fc6668615d192f08e3bdbbc43c0430","datavalue":{"value":"1428432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$48E4029F-D9CB-47AF-8DF9-EF28D9F32936","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a123f282b2302f0d96e53a0d78d446aa74433ca","datavalue":{"value":"computational complexity of set constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975208$F0102109-40E2-498B-8D7E-A4AF03C058A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975208$C7FD5A27-13CE-4B0A-A944-54CE9354207B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975208$D9CA8B48-7BFA-429F-8659-CCC5A0CF2B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7fe2f2415709197ca17d2732570ef76c1e4f0b0","datavalue":{"value":"tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1975208$8FC7C893-4666-4812-9E1C-EE74DC1CD837","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba7232f3f7ae68133198ecf25821b70a187e9eaa","datavalue":{"value":{"entity-type":"item","numeric-id":704043,"id":"Q704043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1975208$6990B4F6-85A6-4DBB-A4F6-B5BD9A32CB82","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":"Q1975208$E3BBDFAC-5562-4EDC-8B02-24257403F452","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"16279d5b64c7b34d7957dcc94703b3d9c28fda1e","datavalue":{"value":"https://doi.org/10.1023/a:1009826603139","type":"string"},"datatype":"url"},"type":"statement","id":"Q1975208$7D4D2DDF-4D81-4EF0-A888-7C08BCEDCA5D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a3ba6ae9e4870ef47d937a6aac9a532cd49cf17b","datavalue":{"value":"W1598816868","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1975208$6D6D36C9-BBA0-495A-ADE5-F66F0FAC2A07","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54bcdda42eb61f07069288fb154450beb0f89baa","datavalue":{"value":{"entity-type":"item","numeric-id":4944863,"id":"Q4944863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"788c208468a312e912f7d2b0865e94b6bbd0cdde","datavalue":{"value":{"amount":"+0.8293250203132629","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":"Q1975208$D6450FCF-5AC3-4BB0-AB3F-7DA48E27B20A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf7a1fd688a9f0e8bb851de9a577524ce268e52","datavalue":{"value":{"entity-type":"item","numeric-id":2506490,"id":"Q2506490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e9d5619e069a4a283ea215a9cb3fa96b78393c","datavalue":{"value":{"amount":"+0.8264477252960205","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":"Q1975208$9069DF67-0EED-49E5-AB16-24533124C98F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"512ad91b4a9a6472c4d792bb43d14c098a2e7b4c","datavalue":{"value":{"entity-type":"item","numeric-id":1271568,"id":"Q1271568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78c4b9b03e98c0153ee061767dede5c3542878ec","datavalue":{"value":{"amount":"+0.8212308287620544","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":"Q1975208$C8E3BF82-6C2C-47C4-BAF8-3D4F68299072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ee5a3dcb1a53cdba0b94b5f46a52b6c52286f6e","datavalue":{"value":{"entity-type":"item","numeric-id":1286366,"id":"Q1286366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"738eb834be61b4574f220c8063b94722d9993404","datavalue":{"value":{"amount":"+0.8097460865974426","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":"Q1975208$E8E60D74-D6D1-45EC-9A8D-A8F93B1439DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1975208","badges":[]}}}}}