{"entities":{"Q807718":{"pageid":809566,"ns":120,"title":"Item:Q807718","lastrevid":64523457,"modified":"2026-04-11T20:27:22Z","type":"item","id":"Q807718","labels":{"en":{"language":"en","value":"On the regularity of matrices in min algebra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4208286"}},"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":"Q807718$A7884C2A-8220-4B7A-A22D-479C05648458","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aa9b35e0051225843385f71ef099c4bcf24a4f50","datavalue":{"value":{"text":"On the regularity of matrices in min algebra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807718$005E27EA-ACE6-438F-9B52-650B06933E5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fab6dc66f36b8ae86ddfc96adaa9597c389a4d19","datavalue":{"value":"0731.15012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$A5E9B06C-D8AB-49DE-8D8F-6DBAF99CFDD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ef19f01c6b326016f6f2954b1ecb7b4157bc31f4","datavalue":{"value":"10.1016/0024-3795(91)90291-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$AF5BFFE3-6CE2-4550-81FC-DA14F3CA0D4C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$6FEAF8D6-8BFF-48E8-A092-A74CAE6308BC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807718$88C6959B-FB11-414D-BB1F-FA68B26D98AB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c6059a7ff238645ff7e105ca31812c479d21cac","datavalue":{"value":"Let \\(G(+,\\geq)\\) be a linearly ordered commutative group. Define an algebraic structure G(\\(\\oplus,\\otimes)\\) on G by setting \\(x\\oplus y=\\min (x,y)\\) and \\(x\\otimes y=x+y\\). The authors consider the set \\(G_ n\\) of \\(n\\times n\\) matrices over G(\\(\\oplus,\\otimes)\\). Note that if \\(A=(a_{ij})\\) is an element of \\(G_ n\\) and \\(X=(x_ i)\\) is an \\(n\\times 1\\) matrix over G then AX is an \\(n\\times 1\\) matrix whose ith row is \\(\\min (a_{i1}+x_ 1,a_{i2}+x_ 2,...,a_{in}+x_ n)\\). Let \\(B=(b_ i)\\) be an arbitrary \\(n\\times 1\\) matrix over G, and let T(A) be the set of all possible cardinalities of the solution set of \\(AX=B\\), where the entries in B range over all of G. It is easy to show that either \\(T(A)=\\{0,1,\\infty \\}\\) or \\(T(A)=\\{0,\\infty \\}\\). The matrix A is said to be regular if \\(T(A)=\\{0,1,\\infty \\}\\).    The authors develop connections between regular matrices and (i) the assignment problem and (ii) acyclic digraphs. The main purpose of this paper is to use the connections and certain well known algorithms to establish a procedure to determine, in case G is cyclic, whether or not a given matrix is regular. The procedure established requires \\(O(n^ 3)\\) operations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$BE569F7F-C249-4764-9905-C0B9CEDDD977","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bbe2dde55566c57c31463992aac9b72d0f8c104e","datavalue":{"value":"15B33","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$EA04EF6F-84F5-4052-AD91-F0B429B156B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06299a38dab9dd1c28e96fe2a7f8cac0943d746","datavalue":{"value":"15B36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$16679C3D-AC9A-47D6-86D0-5BC3F7B05E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$DCF04564-3B8D-4B0A-97CE-C4FAA4CCA4AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$D410EA41-6EDE-4B6D-875C-B5ECCA1B64B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$A7E62793-BB16-4F35-BC85-5677FB0D1539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$4F4BFBFB-5AFE-4944-BF2F-62526A68AE77","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91725df4b39f92d12370b7d18e70b8e7c90dd8df","datavalue":{"value":"4208286","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$AE475857-5165-4B9A-B536-F990EF6AFF4D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dadafa5c5c97430d96d1b300003d079cfe1fdb13","datavalue":{"value":"linearly ordered commutative group","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$7226947E-FF89-4E91-88C0-C3E0B29D2C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"588fa640becdc00717b71605d12d15187788847c","datavalue":{"value":"regular matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$56608FC5-5AF9-4EBE-8566-3A063F194767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9374ed2d3172dd37d5ebf823ec4347cfa78fc4b7","datavalue":{"value":"assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$17DCF3F4-87CB-435C-A877-363608C92A19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d7c8264c25b7a99f5ac67e5fb1c7f116517f04a","datavalue":{"value":"acyclic digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$384A1CE3-1C18-40B2-8399-DA160CB5C2B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q807718$0BB013D8-1A02-4416-B393-465FC1F96CBD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7f9b00e70cc9184062d1b22183cdd374cca76e","datavalue":{"value":{"entity-type":"item","numeric-id":217085,"id":"Q217085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$E11D7659-E8AF-4251-8C99-1C89220873A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ed015f3dd1e59965b1576b5b6a323cd540c0f60","datavalue":{"value":{"entity-type":"item","numeric-id":1254943,"id":"Q1254943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$BF1241FC-5752-401F-9F94-0DF5541221F4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eb445f11ec64d474bebc3aa6f3337ad931fd39f4","datavalue":{"value":{"entity-type":"item","numeric-id":767921,"id":"Q767921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$E7149ECC-9274-41B1-9A7C-854D3318474E","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":"Q807718$78CA6E13-2CCE-4335-9151-992A8FD3E484","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4febfbcfd7adf9c90cfc3b7a9b82bceba34110f3","datavalue":{"value":"https://doi.org/10.1016/0024-3795(91)90291-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q807718$9E089BB6-2943-4D50-861A-C582EE7F8636","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5aedbb6c68c3d84f4f39cd48d5473c212b3cc744","datavalue":{"value":"W1985380143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807718$7A5A9E3F-0C80-4755-A012-ECE797836D2F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d647104b2e4df128a92b136be738c217696a748","datavalue":{"value":{"entity-type":"item","numeric-id":1081608,"id":"Q1081608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$D5500DC1-4215-408B-953E-A754963405AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ce1b78a9a65a9e5aa5d1107722dc82109408fa","datavalue":{"value":{"entity-type":"item","numeric-id":1082274,"id":"Q1082274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$DB2B6EA6-B507-432C-970E-FAE86EDC8B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06f5550e9e145485a3b041a1f682842f5ed5b86","datavalue":{"value":{"entity-type":"item","numeric-id":3964346,"id":"Q3964346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$FAA59322-5AD0-4E15-90C6-82FB6CE95E34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$EA0F0E08-5A4E-4312-A8A6-EE3C09E32789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807718$2FB25DFC-8C77-4C21-8036-9B79758E39A7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed687a632c4d1804701255ae6491698970f35325","datavalue":{"value":{"entity-type":"item","numeric-id":1346691,"id":"Q1346691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"125962274e8158f9ab52c0114424528caf745043","datavalue":{"value":{"amount":"+0.9006673097610474","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":"Q807718$B7F38C61-8A9F-42ED-9E04-37AB716D7ABF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eecd54686418628377889da12150501346d1581","datavalue":{"value":{"entity-type":"item","numeric-id":1355234,"id":"Q1355234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec7237c6aa0745e06e069793ecb9507a2f676f39","datavalue":{"value":{"amount":"+0.8978665471076965","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":"Q807718$CBD85C34-F46D-4FE8-83EF-CFACFDE83505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9761f7ab4563d59745a0f6d63df25c2bb414122","datavalue":{"value":{"entity-type":"item","numeric-id":1082274,"id":"Q1082274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"091de33edeb4d091d155377807ecae7ff9917d9a","datavalue":{"value":{"amount":"+0.8392254710197449","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":"Q807718$B7F47950-DAD2-4081-9E31-981019636E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f639cca249216dc4270fac39f86ae0dc9df32de3","datavalue":{"value":{"entity-type":"item","numeric-id":1406294,"id":"Q1406294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0fa625484b4ec796d98113cb29959a329d5956b","datavalue":{"value":{"amount":"+0.8237816691398621","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":"Q807718$6F5B9C67-9F66-4307-B162-B0A840FF75DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b29aa273eb87a0eb220db071c460915db809e20","datavalue":{"value":{"entity-type":"item","numeric-id":1399940,"id":"Q1399940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf2c2a1b28c9c03e2ce80d9375d1dcfdaa47f158","datavalue":{"value":{"amount":"+0.8224616646766663","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":"Q807718$14BEB67D-A326-4DC2-9036-9C4D990DB29F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the regularity of matrices in min algebra","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_regularity_of_matrices_in_min_algebra"}}}}}