{"entities":{"Q1088407":{"pageid":1099159,"ns":120,"title":"Item:Q1088407","lastrevid":69613611,"modified":"2026-04-13T08:12:49Z","type":"item","id":"Q1088407","labels":{"en":{"language":"en","value":"On the complexity of interval orders and semiorders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3990868"}},"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":"Q1088407$B41EDF27-DB1A-41DF-97DC-1D61727A6130","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9ddbf684bd63a301353637556060b4a7d36fb5ba","datavalue":{"value":{"text":"On the complexity of interval orders and semiorders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1088407$FF5E17F7-56BD-46A9-A412-84932533B540","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed547b68a4846e71e7cdce26affe1411a83210f7","datavalue":{"value":"0612.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$C8A8AAF5-EC6C-4C9A-9B2D-48D93582F150","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"301176c86c49e203959c3023ef971712e5f431d6","datavalue":{"value":"10.1016/0012-365X(87)90003-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$257AA2A2-8B7C-4278-82EC-987991E0542D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a4e46d7f82b5bd7ae5274f9e30daac89c5398cc","datavalue":{"value":{"entity-type":"item","numeric-id":185691,"id":"Q185691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$AC3AB9A1-B66B-47C2-A9D7-749ABA904371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c66a437d74ae466cacad614cef92f8e5d71204e6","datavalue":{"value":{"entity-type":"item","numeric-id":239429,"id":"Q239429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$030E9D9C-6E4E-4DD7-B1E0-869FA96B737B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$743BF42D-7C59-4602-8B0F-A2FEF3D88BB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1088407$58F89D6D-DB0E-4553-A5B2-00BC11CBFDC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eabde64606e11dd063bddc914d5a5f544e8dc9e7","datavalue":{"value":"For an order \\(P_ 0\\), the \\(P_ 0\\)-recognition problem is to decide whether an unknown order is isomorphic to \\(P_ 0\\) by means of pairwise comparisons of the elements in the underlying set. The identification problem asks to determine an unknown order without a priori information.    An order \\(P\\) is called an interval order whenever \\(P\\) does not contain the order \\(2+2\\) as an induced suborder. A semiorder is an interval order which does not contain the order \\(1+3\\) as an induced suborder.    Questions: (a) Is the recognition complexity \\(\\Omega (n \\log_ 2n)\\) for every order on \\(n\\) elements? (b) Is there an optimal identification algorithm?    Results: (a) \\(\\Omega (n \\log_ 2n)\\) is the recognition complexity of interval orders. (b) An optimal algorithm is given for the identification of semiorders.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$B3AA9FE6-624D-4D6F-87F8-A32D28D0C92D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"132effc0cc5e6f5b97c410501e6db3f17df8ce91","datavalue":{"value":{"entity-type":"item","numeric-id":587913,"id":"Q587913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$27DD61E5-2812-4AA2-BB1F-D172FD6770E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$B68494ED-B5F4-4E27-912D-133DA6EFBA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$F2F4CF93-42F8-4869-B9E2-D63E705C0D3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$270288A7-2EF9-4804-8444-3E91CBCD14AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c467716fe9cf2f6a1c2a0c8d46686a4f0c4e8e95","datavalue":{"value":"3990868","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088407$2C240443-4C5B-438F-AEE1-798E095A001E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$395F7494-8BFB-4C8B-82FF-DDED612BF4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22984bcc900ee152aa098a96ff9f86448e8b57a4","datavalue":{"value":"order recognition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$C2A8FE25-AACE-4DE1-A2DA-D119CE59A214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aaafdad03f819aaafbda702709add92e1e7c6d82","datavalue":{"value":"identification problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$0B5747BB-BE5B-4F5C-94B6-3C1D8058CE29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc02b93f05817810227e222ee92dbaee102a4247","datavalue":{"value":"interval order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$554A3309-16B6-4F2C-9183-8FDBAAB3A178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d65a45c51e282ef6e2fffde2271bb93bccee4539","datavalue":{"value":"semiorder","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$33F3688A-2BF5-4FCF-869A-FA2E81479605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f677c29e635ceff06abb2186fae53f4b4789e64a","datavalue":{"value":"recognition complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$F8EE3E6D-33F0-4911-85AF-C9FA262CC104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f439cec38e87484e9e9aa3109d696a578d725bb5","datavalue":{"value":"optimal identification algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088407$0A29C452-5453-4492-A8E4-A852586A2086","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":"Q1088407$7DE5D304-20D1-44EC-8A5E-083D622F3C56","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fc4d0f6a1de7a2eba2ec2594a64008381971e8b","datavalue":{"value":{"entity-type":"item","numeric-id":3686052,"id":"Q3686052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$A0432184-D6C3-4FDF-A3F2-677106C5C3D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$84235306-6B4B-46C0-BD02-B2DB35E7A267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a43354a7750018d1eafd0f96fc1bdf1260efb39f","datavalue":{"value":{"entity-type":"item","numeric-id":5904353,"id":"Q5904353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088407$64EF5B0F-0FFF-4CDD-B588-85682CB63F10","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe0a51cf9cd3cefdc3777e701a508095ba4130d7","datavalue":{"value":{"entity-type":"item","numeric-id":4281648,"id":"Q4281648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d881589df8b948e758cbd8b10ee8dd03c9bf9ee","datavalue":{"value":{"amount":"+0.9147661","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$2291F839-F7B7-47A5-BA0B-E62E5AFE359C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6966662c0633496e33335d00ab974edd819e9678","datavalue":{"value":{"entity-type":"item","numeric-id":1590180,"id":"Q1590180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d881589df8b948e758cbd8b10ee8dd03c9bf9ee","datavalue":{"value":{"amount":"+0.9147661","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$0BDD5E4F-4E0D-471A-A50A-EDF3638AA085","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b376a3387afb6e5df92bc35bc6bcde06f9fe6566","datavalue":{"value":{"entity-type":"item","numeric-id":1937352,"id":"Q1937352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e59da56cec316c30597239005ea84a9ba1e339e4","datavalue":{"value":{"amount":"+0.91217554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$6057CAA7-4FFE-4C44-8099-CC5D3245529B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f952143d5fb03af3a595905268503aa1fda2fa5","datavalue":{"value":{"entity-type":"item","numeric-id":1099050,"id":"Q1099050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c62ae9258896133d847f53c7700d66f884671103","datavalue":{"value":{"amount":"+0.90519696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$27BD21FB-A8BF-4A25-9C65-9600601333E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"478912b84179cef7215b2fde8270110eea59153d","datavalue":{"value":{"entity-type":"item","numeric-id":5273082,"id":"Q5273082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86b63d4eac8abbdf78e4342359c00adfc10cdff7","datavalue":{"value":{"amount":"+0.9045165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$8DBCBCF2-6A10-4EC0-B487-4CCEE30808D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23f22d4066e19f9083e3d40811a34e142d34cd24","datavalue":{"value":{"entity-type":"item","numeric-id":2332813,"id":"Q2332813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f65d4498da74d1f3652aee1b10f01364b4fcefdc","datavalue":{"value":{"amount":"+0.90294635","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$89DC34A9-2ABA-4B29-A54A-72C030905D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4080965bb89b2def8d5aaacdc71bf5bf621ed30","datavalue":{"value":{"entity-type":"item","numeric-id":2741281,"id":"Q2741281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fa27093fafe8aadf9b61c2e28cc79886af95a0f","datavalue":{"value":{"amount":"+0.90052897","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$CDC7CEF1-9563-450F-B695-E173AF130699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ac4b82c821ce4bc1ffa90a7717d0dbca6d09771","datavalue":{"value":{"entity-type":"item","numeric-id":841168,"id":"Q841168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3e8ffc0a00c6601651a0157f153ab423bc7a48b","datavalue":{"value":{"amount":"+0.89861864","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1088407$BE90EB10-353F-4EC8-961D-83EE9338D7E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of interval orders and semiorders","badges":[]}}}}}