{"entities":{"Q819794":{"pageid":821642,"ns":120,"title":"Item:Q819794","lastrevid":64577664,"modified":"2026-04-11T20:50:15Z","type":"item","id":"Q819794","labels":{"en":{"language":"en","value":"Computing border bases"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5016245"}},"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":"Q819794$99B102E3-5961-49BA-B050-6F7DFA3579F9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e1e787e51a30438dff4a08a3b897cd65c1889f0","datavalue":{"value":{"text":"Computing border bases","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q819794$24D664C4-899A-4D27-821A-7A0F39672BE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5c9073a85d52605e68814e1fb9a4627a32807964","datavalue":{"value":"1097.13036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$07CF3E52-1BAF-4927-9CF8-10E1170513B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"56eae99d695d5c657b67435bd0ac350740d006b4","datavalue":{"value":{"entity-type":"item","numeric-id":819793,"id":"Q819793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$393119C7-15F3-4A02-BA16-BED331C43708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71c2a8fd59ff2aea42f2828ebd43ce4734ce1b7c","datavalue":{"value":{"entity-type":"item","numeric-id":515722,"id":"Q515722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$810D4630-21CF-49E4-A80E-4FD9635DF6A3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"34a2791b3d9645796ba9cdff19dd05bcf40f0161","datavalue":{"value":{"entity-type":"item","numeric-id":168348,"id":"Q168348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$BF1CD698-B0A1-4895-95A3-159072ED42CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c49568d53c8ad1554f70d0d5613f2d9e8132fc7f","datavalue":{"value":{"time":"+2006-03-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q819794$C2858419-79FE-4DF4-AB10-3E029F8E70F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1731b92da783936602ae579d7c4d3dea19205fd1","datavalue":{"value":"The authors continue their investigation of border bases [see, e.g., J. Pure Appl. Algebra 196, No. 2--3, 251--270 (2005; Zbl 1081.13011)] of zerodimensional ideals. Although containing more elements, in many applications border bases are computationally more feasible than Gr\u00f6bner bases. In FGLM-like Gr\u00f6bner conversion algorithms border bases with respect to a ``hard'' term order are computed given a Gr\u00f6bner basis with respect to a ``cheap'' term order. For an ideal \\(I\\) in a polynomial ring \\(P=k[x_1,\\dots,x_n]\\) over a field \\(k\\), a minimal reduced Gr\u00f6bner basis provides unique \\(k\\)-linear representations of non standard monomials \\(m\\in LT(I)\\) as linear combinations of standard ones \\(m\\in O=T\\setminus LT(I)\\) in \\(P/I\\). Border bases generalize this approach to arbitrary order ideals \\(O\\subset T\\) such that there is a \\(k\\)-linear decomposition \\(P=I\\oplus \\langle O\\rangle_k\\).  The main result of the paper under review is an algorithm, that computes a border basis \\(G=\\{g_1,\\dots,g_\\nu\\}\\) for a zerodimensional ideal \\(I\\) given by arbitrary generators \\(F=\\{f_1,\\dots,f_s\\}\\) that, in particular, do not necessarily form a Gr\u00f6bner basis with respect to another term order. It works roughly as follows: Fix a degree-compatible term order \\(\\sigma\\). For finite dimensional \\(k\\)-subspaces \\(W\\subset L\\subset P\\) define \\(W^+=W+x_1W+\\dots+x_nW\\), \\(W_{i+1}=W_i^+\\cap L\\) and \\(W_L=\\bigcup_{i\\geq 0} W_i\\) the \\(L\\)-stable span of \\(W\\). A \\(\\sigma\\)-reduced \\(k\\)-basis of \\(W_L\\) with pairwise different leading terms can be computed by induction on \\(i\\). This defines a notion of standard and non standard terms as usual. If applied to the \\(k\\)-span of \\(F\\) within the \\(k\\)-span \\(L\\) of \\(T_{\\leq d}\\) for \\(d\\geq \\max_{i=1,\\dots,s}\\deg(f_i)\\) this yields an order ideal \\(O\\subset T_{\\leq d}\\) of standard terms. If its border \\(\\partial O\\) is contained in \\(L\\) then the border basis is complete. Otherwise increase \\(d\\) and update the data. The algorithm terminates since \\(I\\) is (known to be) zerodimensional. Some improvements using spans within more tight hulls are discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q819794$D7D7637F-C066-46C3-A80D-BC7D5916F192","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$5EFEC826-E361-4199-9F96-5B6078BF3DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e57e2977a9ed0e05339dd5f1673c9f0c9ab91235","datavalue":{"value":"65H10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$7DF8BDE6-FA5D-4028-B67D-C4408108ABA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$F31CC587-0153-407A-A7B5-342E4C0175DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c68f8d1859093483acb07fd4c278652a0648aa99","datavalue":{"value":"5016245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$008B0BFD-25EF-4B31-833D-3004CAF164F5","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":"Q819794$911E0504-C686-4182-856E-4A19F29DFF52","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"333db9978a11e8e2cffeee22a55d4ac5c931c40f","datavalue":{"value":"https://doi.org/10.1016/j.jpaa.2005.07.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q819794$E2A75452-9365-4729-8B4C-3C14D34DBCAE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d6d35bd517073427a7f35a1b6b5ab34aa5775047","datavalue":{"value":"W2116004197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$5DF75B78-8405-4BF2-8EBC-DBC59049C2A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a6340c3aa9cd67064a8033bdc4924d285770a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3806684,"id":"Q3806684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$23199094-BD16-4ADF-B513-E7DF367E62DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebb9dba8fb67f5c936245b1d00a01dc2fa67b447","datavalue":{"value":{"entity-type":"item","numeric-id":4274969,"id":"Q4274969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$6E503A98-751B-4CFB-91B1-F86BC008E45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"477fad7e9eb44ad8a11dffc84ce40c6dfab6c50e","datavalue":{"value":{"entity-type":"item","numeric-id":1295781,"id":"Q1295781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$5BDCE09F-5507-49D5-9E60-2B9371245047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a68a509eadf6111b0e06ec4b721711237d6038","datavalue":{"value":{"entity-type":"item","numeric-id":4660688,"id":"Q4660688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$C8AA4CB9-661B-49C1-AE16-E8CBE41A18FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33e5f9a114f9f2ed0c8a4550007deb312ddd2721","datavalue":{"value":{"entity-type":"item","numeric-id":1318849,"id":"Q1318849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$5594FCB4-D1DC-4210-9018-A8F1343B513D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50af3f972231f34c906a1f07770c69059b1c917d","datavalue":{"value":{"entity-type":"item","numeric-id":1770535,"id":"Q1770535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$7D2446AB-53B4-4406-A130-F6AE31FD35AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c7f3d983cb0969437a1008765e67c723c6449c","datavalue":{"value":{"entity-type":"item","numeric-id":5505187,"id":"Q5505187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$A1477964-1C2F-4693-BC35-B83AB8E38DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eeaa7dfd1d5aa46fe4ef30cb5d8e2f1a04648ae","datavalue":{"value":{"entity-type":"item","numeric-id":4507801,"id":"Q4507801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$526AD104-02B3-4335-980C-68CEF170E260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba39e39f437c7388109153b42a07aec44cecdbc4","datavalue":{"value":{"entity-type":"item","numeric-id":1308641,"id":"Q1308641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$915E8A39-4684-47E6-A24E-0CA3E785CE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0983e33d87026b74eb0bc8ab2da66027d637f0e0","datavalue":{"value":{"entity-type":"item","numeric-id":4502650,"id":"Q4502650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$83827DC0-AFCA-4ECB-9B37-90D723FE5181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dab45334e3943852955e00477efebd5f8b8388f","datavalue":{"value":{"entity-type":"item","numeric-id":4825151,"id":"Q4825151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$B069C3B6-CF57-448F-8915-B2911B51E367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf2a2cf9a1bb52c31ffd60f4cbf304681d2b868","datavalue":{"value":{"entity-type":"item","numeric-id":4861423,"id":"Q4861423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q819794$9A372034-0F2D-4A5C-B192-5ED097D24D2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7254637163e5f45419676e3c3b6e93ba0f4c74f","datavalue":{"value":"10.1016/J.JPAA.2005.07.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q819794$CD2CD6FA-0A70-44C3-B92A-7275BBE89D12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3208ec72f5c41fcd2febf6764a315d1191eb4dbc","datavalue":{"value":{"entity-type":"item","numeric-id":2183743,"id":"Q2183743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d377f98f21ef45d06867a05feeb35e8aa4cbfefe","datavalue":{"value":{"amount":"+0.9462306","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":"Q819794$3CABB8CB-A275-4747-8523-9490BCC205BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b96259b4b66d7750ad317425a442b115e581df1f","datavalue":{"value":{"entity-type":"item","numeric-id":5135747,"id":"Q5135747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70662c646a0cfd1958732cb7ed17b6f49c50a192","datavalue":{"value":{"amount":"+0.89334923","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":"Q819794$6E830B74-606D-4E09-A6EC-9F6921D0B5A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"585cd5d6f6b785a4ad32de50f7746302bc4472ab","datavalue":{"value":{"entity-type":"item","numeric-id":2940363,"id":"Q2940363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"223a3e67ebfe7d4fda6bf02a04007168f4902b47","datavalue":{"value":{"amount":"+0.86508983","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":"Q819794$66332E65-CB7F-4993-9025-C04E0A0A141E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf2d4cfdc1d6c0386fef79b54dcb527ce6733bac","datavalue":{"value":{"entity-type":"item","numeric-id":1943354,"id":"Q1943354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c41ce1c40b5fb78f7bd68291f4e5321203d646b9","datavalue":{"value":{"amount":"+0.8649815","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":"Q819794$B32D520C-2009-4E7A-B78C-C728DF3C91B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eab23304d732743db25aaa184638ac685fd70e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5014657,"id":"Q5014657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59a86aff815eee1c4516089ab3dac1800c26ed8e","datavalue":{"value":{"amount":"+0.8560618","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":"Q819794$FB05D181-D2C7-4411-BB0D-074CD6E02347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"759f512121bcf3e1087bf47bd77e9372b175ce4a","datavalue":{"value":{"entity-type":"item","numeric-id":534027,"id":"Q534027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4acaeaf0e5db336f9053f43ef7e4122aa81c856a","datavalue":{"value":{"amount":"+0.8556206","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":"Q819794$9C52D850-05A5-4D60-BF17-34A9E381BFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d34a9321f3ae252be92f45d8dc475d43fb3bb78d","datavalue":{"value":{"entity-type":"item","numeric-id":1770535,"id":"Q1770535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d131f90c5a09ec1b7d03da2c12547210acb89ff9","datavalue":{"value":{"amount":"+0.8423197","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":"Q819794$322F7587-8B8C-4AE0-A180-C5663137D406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ea04724f93eb6f37ad20d19a62f116107a482e8","datavalue":{"value":{"entity-type":"item","numeric-id":5383882,"id":"Q5383882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c20ff252691c5e9ff4a7b093eb536582a901a0eb","datavalue":{"value":{"amount":"+0.84074754","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":"Q819794$CE3CA507-B68B-48AF-83B5-E89B1857B0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5390c5403c5257037e4a67b0c864fc986ef8d6a2","datavalue":{"value":{"entity-type":"item","numeric-id":5254148,"id":"Q5254148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89371a882b5f0d067fb703035efc05529feb332f","datavalue":{"value":{"amount":"+0.831136","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":"Q819794$3F114669-8123-4A4E-BFCA-8275D074A505","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing border bases","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_border_bases"}}}}}