{"entities":{"Q474731":{"pageid":476498,"ns":120,"title":"Item:Q474731","lastrevid":62095437,"modified":"2026-04-11T03:44:39Z","type":"item","id":"Q474731","labels":{"en":{"language":"en","value":"New algorithms for bidirectional singleton arc consistency"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6373257"}},"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":"Q474731$47475DF7-BE89-4063-8FBF-3961BB21B2B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e1940bee800cdfd1b00c71a76152d6ce17175cda","datavalue":{"value":{"text":"New algorithms for bidirectional singleton arc consistency","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q474731$6E469731-E83D-4A86-BF40-6DB112E53A91","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b3735dc0b8966e8f18116683c4ba7335b49a5ca","datavalue":{"value":"1299.68150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$134C7C40-A11E-44F9-8CED-89D286D39DDB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b284ac8860b5ccbc3c30bc67ad35afbbfec0c8c","datavalue":{"value":"10.1155/2013/904768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$EE0DB1E5-3561-4BB5-B415-7130EB8283CD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be94d47102d8740d5bad660b065da96475ab52f5","datavalue":{"value":{"entity-type":"item","numeric-id":474727,"id":"Q474727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$8BFA9E3E-6641-4A11-97EF-DD926A0D94E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06bfd008968ae7865bfbc776775cd1dd79a5cf51","datavalue":{"value":{"entity-type":"item","numeric-id":474728,"id":"Q474728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$E45D0873-F393-4459-9800-206BA58D928D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a786a3a23e9733819a17ef9b6145d2957de8ae11","datavalue":{"value":{"entity-type":"item","numeric-id":474729,"id":"Q474729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$2F4B546D-A1AB-49A9-B941-87914738E4C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"793337ee812276d0591ceae203c80f64af655860","datavalue":{"value":{"entity-type":"item","numeric-id":474730,"id":"Q474730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$018D5C13-0255-414C-9D95-50BA8802B49B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80121cc84c7f101d26f84b1b6c864b4c33b9d4e3","datavalue":{"value":{"entity-type":"item","numeric-id":249536,"id":"Q249536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$79744F23-7A32-46A2-9F52-8F03D97AB687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"69ea9683847f6c6a7b2313ffd0a9d7967baab821","datavalue":{"value":{"entity-type":"item","numeric-id":1719491,"id":"Q1719491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$FB81C677-8164-4E3F-A824-1D9616176C94","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$5953CA3D-031F-4C91-94FB-F33A07FCFECA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"baf80493586065a1490747a28bc7db754b9ba183","datavalue":{"value":{"time":"+2014-11-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q474731$9179C51C-6079-48B5-B5C6-EDF2C6B30C50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"14f341319652150e36c4025f962973ebe600d9b8","datavalue":{"value":"Summary: Bidirectional singleton arc consistency (BiSAC) which is an extended singleton arc consistency (SAC) has been proposed recently. The first contribution of this paper is to propose and prove two theorems of BiSAC theoretically (one is a property of BiSAC and the other is the property of allowing the deletion of some BiSAC-inconsistent values). Secondly, based on these properties we present two algorithms, denoted by BiSAC-DF and BiSAC-DP, to enforce BiSAC. Also, we prove their correctness and analyze the space and time complexity of them in detail. Besides, for special circumstances, we show that BiSAC-DF admits a worst-case time complexity in \\(O(en^2d^4)\\) and a best one in \\(O(en^2d^3)\\) when the problem is an already BiSAC, while BiSAC-DP also has the same best one when the tightness is small. Finally, experiments on a wide range of CSP instances show BiSAC-DF and BiSAC-DP are usually around one order of magnitude faster than the existing BiSAC-1. For some special instances, BiSAC-DP is about two orders of magnitude efficient.","type":"string"},"datatype":"string"},"type":"statement","id":"Q474731$EEFD23DE-DDF3-4C7D-8159-5398446A627C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$F414B99F-53F1-48E0-A95B-3C3578E91DD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7e38c376e9d5c8f1b8f5ed4031edff655e0001ec","datavalue":{"value":"6373257","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$182E25C5-9BA0-458D-B2E7-E87524CAF5E5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fef1f5520f3770435f4290fae5cc33f88a42d06b","datavalue":{"value":"Q59029432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$B3DAC5D2-8779-406A-B81D-078A4CBB3870","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":"Q474731$BB8272E0-0C18-46B2-9796-FAF956EF536D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"098ee825b007ceeff5a056cfc0801c85bb183efd","datavalue":{"value":"https://doi.org/10.1155/2013/904768","type":"string"},"datatype":"url"},"type":"statement","id":"Q474731$F740A06A-0C5C-4A18-9372-299E361096AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2ee468406d4486c299987e79e542b25fa9b463bb","datavalue":{"value":"W1985829054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q474731$B24E9466-19A2-4D2F-B735-D0997D811275","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b84361433057f8580c286b3014ac2dce5767ba68","datavalue":{"value":{"entity-type":"item","numeric-id":2457664,"id":"Q2457664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$D6BEA751-1067-4340-90B6-6948352C7ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bc7b0f82e42c56ee306811b6c3df8af19432e03","datavalue":{"value":{"entity-type":"item","numeric-id":1231783,"id":"Q1231783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$EB93929B-20AC-4600-86CB-00ACDA9D225B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db859b8619008974006d015bfb23f842720f56ed","datavalue":{"value":{"entity-type":"item","numeric-id":4473037,"id":"Q4473037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$D8AF6535-C511-4A8D-B29C-84EB942DE763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ec2fe816489cddbe798cac7afbef043c8dff21f","datavalue":{"value":{"entity-type":"item","numeric-id":2389615,"id":"Q2389615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$54AC8612-AE81-47F7-BFFA-1A9D3D6EC689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"448910d87e19bcf3d507dba8f9ecca33be8c460e","datavalue":{"value":{"entity-type":"item","numeric-id":5949019,"id":"Q5949019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q474731$F67DD05C-A5E3-495B-A2FB-B9383149DDE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ca282102286307df67568f6e00d1b9ccf3b4ab5","datavalue":{"value":{"entity-type":"item","numeric-id":2430358,"id":"Q2430358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebbdd8ce5601d9551d05ba74bdd3a403288650a5","datavalue":{"value":{"amount":"+0.9349289","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":"Q474731$11458BCD-9CC7-4A30-BE31-53F4332D26F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"804d2579f75bdb0c8e0ef535d467016a0bf75355","datavalue":{"value":{"entity-type":"item","numeric-id":2389615,"id":"Q2389615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bb5ea820d28ec6d0af42ddfd23c31ca72b824cc","datavalue":{"value":{"amount":"+0.88997114","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":"Q474731$AEE09EFA-13DA-489D-B107-36DD900E91C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a3c17bc1fc2eb3b915990fa52fecd2ed97eea1d","datavalue":{"value":{"entity-type":"item","numeric-id":1380133,"id":"Q1380133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7da2118dd0ea499a077060efbcff3a6362348dc1","datavalue":{"value":{"amount":"+0.8675111","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":"Q474731$C570FF31-8AD1-40C6-9B3D-9622F908B749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82b9a1a495e347ad51cfd9c5e5c7b7bb929f94ae","datavalue":{"value":{"entity-type":"item","numeric-id":1199922,"id":"Q1199922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0587d9a278b8d8756b106b0f876f708bc55930a","datavalue":{"value":{"amount":"+0.86431354","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":"Q474731$8AD3E6F9-E763-498F-A047-A912B391BEE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5fa66673411bde31a0591cd77074fc8b3cafb65","datavalue":{"value":{"entity-type":"item","numeric-id":1871973,"id":"Q1871973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1333f9ae2f694e6319ccf7fa74fb4bbdff69f7a","datavalue":{"value":{"amount":"+0.8485454","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":"Q474731$66389572-2958-451C-9D05-D26E5143D717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"add44877bf9120939ac269cbb3ea4a767fc9652f","datavalue":{"value":{"entity-type":"item","numeric-id":2767070,"id":"Q2767070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77c5dd4b01f064795e76f58c5698789ddc050710","datavalue":{"value":{"amount":"+0.8434423","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":"Q474731$57972DB7-C065-419E-9736-FACA23F86C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e193ca08d7ba68d1173fa2af5503c38cd750ef4","datavalue":{"value":{"entity-type":"item","numeric-id":4424854,"id":"Q4424854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61aca7870a8e1d94f12076e2755dbe949b7e9484","datavalue":{"value":{"amount":"+0.835218","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":"Q474731$151A073C-FDFD-43B1-9C4A-D94D86DF5250","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New algorithms for bidirectional singleton arc consistency","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_algorithms_for_bidirectional_singleton_arc_consistency"}}}}}