{"entities":{"Q1575136":{"pageid":1585876,"ns":120,"title":"Item:Q1575136","lastrevid":47026584,"modified":"2025-12-26T01:56:22Z","type":"item","id":"Q1575136","labels":{"en":{"language":"en","value":"Games and total Datalog\\(^{\\lnot}\\) queries"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1493146"}},"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":"Q1575136$0B0F1159-5E4E-43CD-9D15-01EE2C61B18D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d0da5ac7973d3a0c289054983c3566fe39e5e718","datavalue":{"value":{"text":"Games and total Datalog\\(^{\\lnot}\\) queries","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1575136$CDBE4C6A-FECC-4F53-907E-40D3F5A567D8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd9dee260e5d97dd22ff67904c9b2a51279220d8","datavalue":{"value":"0947.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575136$E55D07F5-39BA-492E-8504-1CD8402E96DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"52cb99e5fa688513b0e478800eb5703773ba1b9f","datavalue":{"value":"10.1016/S0304-3975(99)00222-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575136$44349A92-D373-4FD0-8C86-1197680B31BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e32d65d787fe0d6ecf5ead2ab2b33757d6f00590","datavalue":{"value":{"entity-type":"item","numeric-id":1575134,"id":"Q1575134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$268E43DE-EB29-432F-8AEB-CBC572AE8973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"533e6a2f2483a32398b8daadaa250165970e45d9","datavalue":{"value":{"entity-type":"item","numeric-id":490658,"id":"Q490658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$CAC53EA2-A556-4808-9AC5-6DAEF96459E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eeccedc5657d49d789ba0f69299465f1a71ea4b2","datavalue":{"value":{"entity-type":"item","numeric-id":861914,"id":"Q861914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$431891A2-A967-4155-BB83-85D208C5CC9E","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":"Q1575136$1564017E-98D7-4919-8562-34478BF33BB3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3a497233c3b9babc42d370358782cbff338a7a1","datavalue":{"value":{"time":"+2000-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1575136$38316581-B146-4726-8D77-8D4D65BB3087","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4892a22739c89c91c393d410355c2bfe3febbc03","datavalue":{"value":"We show that the expressive power of Datalog\\(^{\\lnot}\\) programs under the well-founded semantics does not decrease when restricted to total programs thereby affirmatively answering an open question posed by \\textit{S. Abiteboul, R. Hill} and \\textit{V. Vianu} [Foundations of databases (1995; Zbl 0848.68031)]. In particular, we show that for every such program there exists an equivalent total program whose only recursive rule is of the form  \\[ \\text{win}(\\bar{X}) \\leftarrow\\;\\text{move}(\\bar{X},\\bar{Y}), \\lnot \\text{win}(\\bar{Y}), \\]  where move is definable by a quantifier-free first-order formula. Also, for the noninflationary semantics we derive a new normal form whose only recursive rule simulates a version of the game of life.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575136$0DF268CC-02AA-4AF2-8404-6367F83171BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575136$4D645529-B275-434D-82B0-47C652DD3A30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"576b6121ef2b0566b02e7a612981aaeb49629d09","datavalue":{"value":"1493146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575136$D421B36E-35B7-4AD6-929F-15AB5AF67C28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb738c59bd69ca062534f6dd33dac742b97beb18","datavalue":{"value":"datalog","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575136$17EEFE8B-6DEF-4821-8A7B-76A94086107C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"829ca1e536ef76ef92ed2ab157d10567452023f4","datavalue":{"value":"well-founded semantics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575136$A5381F70-8DB7-4F74-A561-37E115A3C716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"921d0cf0bf3bc2fc4a883887badbee0f5c430e90","datavalue":{"value":"fixpoint logics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575136$E8F7AECF-8534-4298-BBF3-B19660E8E841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4dc9a47c8de051a880f2e514b2df8fca32ac201f","datavalue":{"value":"games","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575136$F010C7B1-066A-42D6-BAF9-E6EB6F86C4A2","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7545068a6822e4e652ce3b521c8f6365c7bdc7b9","datavalue":{"value":{"entity-type":"item","numeric-id":31846,"id":"Q31846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$445110D4-5904-48F6-B831-06CEDE93C8BA","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":"Q1575136$A49E2447-473A-48B5-9452-1AC4813B9AD1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae600d82e59da48d9490ff29ee5b51a547bc0409","datavalue":{"value":{"entity-type":"item","numeric-id":4864249,"id":"Q4864249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$34115015-0235-49BA-9B2E-2D573A252D49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7c59a420561f0981f327db098a9b1c0858252a","datavalue":{"value":{"entity-type":"item","numeric-id":756410,"id":"Q756410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$C78A7B0B-B9BD-4329-A10D-5D3B54827CDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b061c74acfe7ed299eeb2c95c750dc4bed6741a4","datavalue":{"value":{"entity-type":"item","numeric-id":1176285,"id":"Q1176285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$DF43DE50-ED5B-4D95-97C5-CDD3A62391D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d2c32b298b09103f7cc9eabedf752dc67f406d3","datavalue":{"value":{"entity-type":"item","numeric-id":4850061,"id":"Q4850061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$B06FECE4-65EC-4890-92C8-DDCE428154EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4f2ee72898110fe7889fd717779f041df5428e7","datavalue":{"value":{"entity-type":"item","numeric-id":4866342,"id":"Q4866342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$4715D73C-E368-4825-9219-EBD8BC43003E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a675fab4321817783597d6a1b8160efcb24c4ec","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$356556A9-10D5-4729-A3D4-811DEE82902D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0f7a9134e658e259af7b343ab5d0a31a19e0988","datavalue":{"value":{"entity-type":"item","numeric-id":686646,"id":"Q686646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575136$4B334ADF-2644-4825-B656-7CB01758196D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"37a614a30d7845d04df1a61b2a2a04c0be9e8636","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(99)00222-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1575136$3E60E21D-01F0-4FB0-9781-48A0671F8118","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5e95718feae25c14e5950d5acef40d72cdbe2cc7","datavalue":{"value":"W2117344057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575136$02FF5206-7E9C-4DE7-8AB2-C3AA7E5056C1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"210bcfe99326042e2936b719e031f0e51ab93ff6","datavalue":{"value":{"entity-type":"item","numeric-id":960526,"id":"Q960526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e121008d59346e12955915c3e0261804d17120d7","datavalue":{"value":{"amount":"+0.7755853533744812","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":"Q1575136$717BCB03-D5B3-43B5-BEAE-2EA5AEAF5A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89ab249c1aa61056718dc4bfc57822e4c2659ef3","datavalue":{"value":{"entity-type":"item","numeric-id":756410,"id":"Q756410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3093bf630b5b9ffcb7e54d3dd06d7aae9e80c85f","datavalue":{"value":{"amount":"+0.7675950527191162","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":"Q1575136$E852F4E9-6120-4A8B-AFEA-2C600F7A9F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df36bb4345f8ff9d9981b513103ada40184284d6","datavalue":{"value":{"entity-type":"item","numeric-id":1176286,"id":"Q1176286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a64670aca95f0229a3e207d3d71ef70fe25392","datavalue":{"value":{"amount":"+0.7600058913230896","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":"Q1575136$9D1725AC-F436-4794-ADD3-399F2D26C830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b373978be27576a06e061ddcffc43b003803ab7","datavalue":{"value":{"entity-type":"item","numeric-id":4302849,"id":"Q4302849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ceb3022320881e5431ad2e0d253d21e34b1ba962","datavalue":{"value":{"amount":"+0.7464089393615723","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":"Q1575136$985994E7-0A68-4C01-8960-155696CA6DF2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1575136","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1575136"}}}}}