{"entities":{"Q1104095":{"pageid":1114847,"ns":120,"title":"Item:Q1104095","lastrevid":49176823,"modified":"2026-01-06T17:22:52Z","type":"item","id":"Q1104095","labels":{"en":{"language":"en","value":"Parallel complexity of logical query programs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055048"}},"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":"Q1104095$B7205A1D-CB07-4357-BA89-66FD09BEB45B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cca9fe7feda4d4a468a74039dbf1ffba3037b0fa","datavalue":{"value":{"text":"Parallel complexity of logical query programs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104095$27FF964B-874A-421F-9B6F-ACC8E3885B6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"472c5031c98d00f09c0fc7a619aa0ccf93ae032b","datavalue":{"value":"0646.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$8BB49B3C-5B04-434E-B1AB-4411F65686B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3542c1b6d9ae5ed5def0ccc025b277457d14c52f","datavalue":{"value":"10.1007/BF01762108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$936A0AA8-C8E3-4D6A-B3FA-630219767C3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c92f39d6928481f389c4da6679a27b0ca13b096","datavalue":{"value":{"entity-type":"item","numeric-id":269331,"id":"Q269331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$A7B7B2BC-0EBB-4AFB-9D3E-4EF0EC09A749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"efe49c25650dcd4febba639d323fee3054738fd4","datavalue":{"value":{"entity-type":"item","numeric-id":1104094,"id":"Q1104094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$4A8D66BE-7DCB-462B-A9B0-1E7D35AAE551","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$54911CFC-4E29-4A00-8BD8-038D93ADF1C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1104095$AC2AAF06-D759-4FC7-BC69-2C95C3960935","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b16e1331c56a7c81fd7eeda320f324771a92d9df","datavalue":{"value":"We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the ``polynomial fringe property'', this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the ``linear'' and ``piecewise linear'' classes of logic programs are in \\({\\mathcal N}{\\mathcal C}\\).    Then we examine several nonlinear classes in which the program has a single recursive rule that is an ``elementary chain''. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the ``polynomial fringe property''; hence such programs are in \\({\\mathcal N}{\\mathcal C}\\). Finally, we describe an approach for demonstrating that certain logical query programs are log space complete for \\({\\mathcal P}\\), and apply it to both elementary single rule programs and nonelementary programs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$F9B5DF29-E014-48EC-A89C-FC928CF4D594","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$86C8D145-0CEC-45FF-9946-97A0A8068324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$933B682A-D5B0-4470-A067-6C370F45FE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$4D635DD6-DFFE-4ABF-9C84-52447FAF37FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$BDAED4F8-95B4-4601-AB26-CF9948235A5F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e42471c385477c2e7cef3e56af5d9bf0671b880","datavalue":{"value":"4055048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104095$2572AA13-F7FC-45F1-AE29-772F6DD15A91","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb6a05e66286943e12d84cc07a37860d5307d960","datavalue":{"value":"chain program","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$4505F63C-3D74-47E4-80B8-612E921F0006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d75d448735778f46c4e9667e177539a844422b26","datavalue":{"value":"context-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$9A989A75-00F0-4AE8-ADD9-DDD3D58C6D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51fe650d748b2989ba99ad2aca7c65f3249ff435","datavalue":{"value":"generalized sequential machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$F22F3E4C-84B3-47B8-A528-8DC6B5851AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c2c58bcb25c86700471c3f7fb73aca174b7f439","datavalue":{"value":"parallel time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$9614A338-9E98-4F38-94E4-85A86D549830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0aa02e9e8f1d2c4fcc62f7a423a9975b0eaaeca","datavalue":{"value":"logic programs without function symbols","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$7CF6124B-23E5-49F4-B928-F22C81E96D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6263175475b06fd3992e252c6d8e14e739eff59c","datavalue":{"value":"logical query programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$98FD9CC8-876D-4E7B-804F-03A3A52969BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d66e2b04c20dd8604424317ed54fc5de69e54d6d","datavalue":{"value":"Datalog programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$AB118E59-48B1-4504-9E22-5199009ED40D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd23fe76792d802c489e2afc027cf2c6d5878f68","datavalue":{"value":"PRAM algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$05197BF7-E334-4C86-8C4E-90E1B361C1A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1c744c3ce154a6e053fe88750c1a403e4d23968","datavalue":{"value":"polynomial fringe","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$736463B9-ECAB-4163-9C0D-648508655B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bb741969c539638e4268aa13dfe2af7b2343c51","datavalue":{"value":"\\({\\mathcal N}{\\mathcal C}\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104095$F1CE23A0-90B0-4E99-8ACB-1C225EDDAC40","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":"Q1104095$12BF67C8-E047-4E64-87D4-7A0BCB200E1D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9244cfa0cc83c54f6dddc3fcd9671a0260655de","datavalue":{"value":{"entity-type":"item","numeric-id":3942361,"id":"Q3942361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$9E7C57CC-4000-44EF-AB02-F3D34B30D680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04199e03d1d3ec0d2b5fbfff526a164b91654871","datavalue":{"value":{"entity-type":"item","numeric-id":1838840,"id":"Q1838840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$8D0D9A68-F80A-467E-924E-B0324B7391D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0445ca81f1046c8b5bea1a2062f174b139078383","datavalue":{"value":{"entity-type":"item","numeric-id":1217591,"id":"Q1217591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$52755637-940D-4EC4-9653-5A6813A9275D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$EAF4CD5D-65C6-4D69-A77C-202A6682D890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4cda73737862ae25acf95e82a813fd5a18542be","datavalue":{"value":{"entity-type":"item","numeric-id":5525346,"id":"Q5525346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$83C33417-59D3-4B23-9C91-1BF74B560B3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ac9e6b5b6cf386d5e282046ca2407a9abb9a6ff","datavalue":{"value":{"entity-type":"item","numeric-id":5538917,"id":"Q5538917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$0B4DB279-57D1-46C6-A620-53D746135E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$87FFB785-70D3-4065-B348-46336642BE97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$83DCF424-7C8D-4614-9734-E14FBAC0EC9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$910D2899-5BB8-4794-80C2-A33E1D095EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49ffc4ffae19106f4c78c37658090ee0460f8f76","datavalue":{"value":{"entity-type":"item","numeric-id":3727384,"id":"Q3727384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$877B710B-5C82-451C-AA6E-8ADC5DBC5CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$1D857ACA-0473-4820-BCB3-CBC771FCEDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a48527afe062074df34bbd14824dbb74200fe9e1","datavalue":{"value":{"entity-type":"item","numeric-id":3702512,"id":"Q3702512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$5AF24DD8-3448-45E7-8E95-B3B7C4D0765C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f450486e6dd81b9bc183a0057d83ff04fd2d4632","datavalue":{"value":{"entity-type":"item","numeric-id":3316595,"id":"Q3316595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$A0C14D9C-822E-47BE-BDB2-D3BE76EB1AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1e2a210a633c08ab99ee4d2a519f4798177e87","datavalue":{"value":{"entity-type":"item","numeric-id":3036703,"id":"Q3036703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$F545DF65-29EA-4BCF-AA19-DB41A5A609D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5f91daa2195cbe510cefc59ffaafa18b1c28390","datavalue":{"value":{"entity-type":"item","numeric-id":4107888,"id":"Q4107888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$904F6620-505A-4E81-A697-8407FBE403AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59db4828c7fab26ad356c64453834c24c3294ede","datavalue":{"value":{"entity-type":"item","numeric-id":3348436,"id":"Q3348436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104095$D8971F11-1D09-4E67-AC1F-2B4A383EADFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0459704bf6324286362909b8d3eab826b141769","datavalue":{"value":{"entity-type":"item","numeric-id":1202885,"id":"Q1202885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"680feb131d3b58d925b11fc9e25950d75e6cef71","datavalue":{"value":{"amount":"+0.9152034521102904","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":"Q1104095$2E072342-11ED-4251-8A77-EB8BB3126948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7852997bc5a74f6f12f22dba680c6ddcbc48638d","datavalue":{"value":{"entity-type":"item","numeric-id":4271089,"id":"Q4271089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3515040d4fb8824b5f492c273c173b184456ca61","datavalue":{"value":{"amount":"+0.8491712808609009","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":"Q1104095$A75E4B2E-4432-41D4-A227-F844306A4144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1190f1d5dfc606c0f86e094b60449d755715ea22","datavalue":{"value":{"entity-type":"item","numeric-id":3786037,"id":"Q3786037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c628b70d290c21b4186d756f8013faf9c6e6f22","datavalue":{"value":{"amount":"+0.8281204104423523","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":"Q1104095$4A42D501-4310-475A-AEAD-663CBF2D15E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2e1626b0a6735f440f63aef071b7401fb88a47a","datavalue":{"value":{"entity-type":"item","numeric-id":4015953,"id":"Q4015953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5007b8449cf87ad02854aa064873b0a61a1cbe89","datavalue":{"value":{"amount":"+0.7977551221847534","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":"Q1104095$4F881CFC-1978-437C-A350-D7423EFB581E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5120764ee68d581ef4404dad279e3c72a875e0e","datavalue":{"value":{"entity-type":"item","numeric-id":696953,"id":"Q696953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"415a3e772dd999aa16f6d8e7544c7975c1d78aff","datavalue":{"value":{"amount":"+0.7857556343078613","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":"Q1104095$E647628A-2EEC-4C31-8A6A-EB4FF5E907CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104095","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104095"}}}}}