{"entities":{"Q810043":{"pageid":811891,"ns":120,"title":"Item:Q810043","lastrevid":64544310,"modified":"2026-04-11T20:36:45Z","type":"item","id":"Q810043","labels":{"en":{"language":"en","value":"A lower bound for the recognition of digraph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4212080"}},"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":"Q810043$25D6BE1A-1E4E-44EE-9F6A-9B6F10825810","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e49eeb851523eec575bb112aded39013c2738f9","datavalue":{"value":{"text":"A lower bound for the recognition of digraph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q810043$974BE649-9312-4B8C-851F-1D7CE6EEDBAB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af391edf7a4566551694c9740e5110dc5482b68a","datavalue":{"value":"0733.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$17411BD1-5164-48C8-8ED4-386F7E228F74","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fc6dde99f64dcb2628b03cf1ba5b6bac17b4c10","datavalue":{"value":"10.1007/BF02122695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$078147A6-6DC2-4432-9779-B2881F937A59","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$78BA0FB4-168E-49B1-88EE-F556AE32ADCD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q810043$4AA5BD5A-6750-4B39-9D2E-71CE1B2B4370","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15fee0ab888d80b939cacb09e56498d211a95cff","datavalue":{"value":"A digraph may be viewed as a subset of the edges on the node set. A collection of such digraphs is called a digraph property provided that it is invariant under renumbering of the nodes. The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case. It is shown that every digraph property which is monotone, being not distroyed by the deletion of edges, and nontrivial, being held for some but not all digraphs, has a lower bound of \\(v^ 2/2-O(v^ 2)\\) for its complexity, where v is the number of nodes in the digraph. In addition, it is shown that a certain class of monotone, nontrivial bipartite digraph properties is evasive, requiring that every entry in the adjacency matrix be examined in the worst case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q810043$2BE6C854-149E-434D-8E00-E424FC4F15B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$53CB3164-971F-48EA-B9D0-6227573FA56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$FD255EAF-F4C9-43DF-981C-BAF7AA458AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$628FD5E8-6C90-4EB6-8D4A-304A60DA4236","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"29180bb789e7f41d0ea93f2c281fde4d0a715800","datavalue":{"value":"4212080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$6D22F20B-0123-4A61-9521-642D1247AD50","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q810043$445D29DE-3DBD-4834-B727-A96C759E451D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q810043$EEED1D20-7F24-4EE3-9547-3D0894170E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q810043$3542C435-D5DC-4E63-880B-CF7DEF9B4253","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a0a57cd83a690b4e7a99576fe9a7af57a0de1c1","datavalue":{"value":{"entity-type":"item","numeric-id":290235,"id":"Q290235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$F71EE012-0D21-4E64-BD84-2DA625C88E6B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$C26C63F8-02CB-42A6-B200-A61B463A58D4","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":"Q810043$D4BD51D5-5C4C-4CEE-A2FF-69FC93E113CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb40aa93777a7cd41d54dcf43b55867cf1b75c38","datavalue":{"value":{"entity-type":"item","numeric-id":5772619,"id":"Q5772619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$41B91961-9E81-4DED-8355-EA3C7A0130B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c28903e6085f325f83f6c2f8674c9e4abb77407","datavalue":{"value":{"entity-type":"item","numeric-id":1065831,"id":"Q1065831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$3A65938A-FA00-4D5C-BD48-FFA8DAC6B474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdeabaf1f4b0dab31866cc696f100a2bc7edf8a0","datavalue":{"value":{"entity-type":"item","numeric-id":1237992,"id":"Q1237992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$E61B60BD-C5E2-4AD4-B319-8FCEF3F55E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da076d31b85049ed80c18404d1e826383b07b223","datavalue":{"value":{"entity-type":"item","numeric-id":1216889,"id":"Q1216889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$B0DDC0C9-BFD1-4845-A999-EC44C331997D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$2C327388-EA4C-4BDD-BE61-33ECC14146F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"465d3d91e9c619710494e58600d45f7ef993e5f8","datavalue":{"value":{"entity-type":"item","numeric-id":5778455,"id":"Q5778455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$F839A841-9567-4D7A-A082-93818B3F6161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cefcb0d68060735568a4211c0151369b4dfb2c05","datavalue":{"value":{"entity-type":"item","numeric-id":3792707,"id":"Q3792707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810043$441CAE94-AF45-4CEA-9DD7-08FD125067AE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"02864851792da6d1b54ce9ef4fde88a593b8221b","datavalue":{"value":"https://doi.org/10.1007/bf02122695","type":"string"},"datatype":"url"},"type":"statement","id":"Q810043$F6ACFC63-5B97-420E-AE7B-3BC1C13D8029","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d583a5c0459504f5bb6900bcbb757634e1ad7f02","datavalue":{"value":"W1980974491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810043$3A5F3411-3955-48D7-870C-68E851A6D69E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7643027ac245a0e31431571fc7df9646fb69c4d7","datavalue":{"value":{"entity-type":"item","numeric-id":653841,"id":"Q653841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"099f1eedfb4e58abf1d8c54d5e20ca1aaaedf3dc","datavalue":{"value":{"amount":"+0.8360362648963928","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":"Q810043$BF148468-4339-4546-895D-D0344152F186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c01298b1f3918107dc40c5e3a97afab7a6a521","datavalue":{"value":{"entity-type":"item","numeric-id":1180407,"id":"Q1180407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7775fd119240f77dcd1e0d26a389320b59615cf","datavalue":{"value":{"amount":"+0.8121211528778076","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":"Q810043$32D751E2-BD57-4A4B-A432-52E98E7E0EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd292f0e82ac15aed76d058757a6d7254156d460","datavalue":{"value":{"entity-type":"item","numeric-id":3792707,"id":"Q3792707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6f47388457db7529f1332e449574645a5863f84","datavalue":{"value":{"amount":"+0.808111846446991","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":"Q810043$11B60543-82A6-4454-9FCC-322CA472108A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b200024ae346de62affbd9c005c4d3a8e3b04c08","datavalue":{"value":{"entity-type":"item","numeric-id":6370303,"id":"Q6370303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4195f2df622e7ab934abb9b435494a795ee39216","datavalue":{"value":{"amount":"+0.7966204285621643","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":"Q810043$1BB552F6-2D62-428C-A069-D75D7D9A72DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6acbdff414de20139df4acca23d8c7aa03c5f661","datavalue":{"value":{"entity-type":"item","numeric-id":1825645,"id":"Q1825645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3f055f312a220c73a2ed8ecba24ad5cb1dc3fd7","datavalue":{"value":{"amount":"+0.7935614585876465","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":"Q810043$7C34B6F7-C041-4FE3-8119-1E6444560DE5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for the recognition of digraph properties","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_the_recognition_of_digraph_properties"}}}}}