Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętySolvability of orbit-finite systems of linear equations
| cris.lastimport.scopus | 2024-02-12T19:47:41Z |
| dc.abstract.en | We study orbit-finite systems of linear equations, in the setting of sets with atoms. Our principal contribution is a decision procedure for solvability of such systems. The procedure works for every field (and even commutative ring) under mild effectiveness assumptions, and reduces a given orbit-finite system to a number of finite ones: exponentially many in general, but polynomially many when the atom dimension of input systems is fixed. Towards obtaining the procedure we push further the theory of vector spaces generated by orbit-finite sets, and show that each such vector space admits an orbit-finite basis. This fundamental property is a key tool in our development, but should be also of wider interest. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.conference.country | Izrael |
| dc.conference.datefinish | 2022-08-05 |
| dc.conference.datestart | 2022-08-02 |
| dc.conference.place | Haifa |
| dc.conference.series | IEEE Symposium on Logic in Computer Science |
| dc.conference.series | IEEE Symposium on Logic in Computer Science |
| dc.conference.seriesshortcut | LICS |
| dc.conference.shortcut | LICS 2022 |
| dc.conference.weblink | https://lics.siglog.org/lics22/ |
| dc.contributor.author | Lasota, Sławomir |
| dc.contributor.author | Hofman, Piotr |
| dc.contributor.author | Ghosh, Arka |
| dc.date.accessioned | 2024-01-26T07:52:52Z |
| dc.date.available | 2024-01-26T07:52:52Z |
| dc.date.issued | 2022 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.identifier.doi | 10.1145/3531130.3533333 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/120188 |
| dc.identifier.weblink | https://dl.acm.org/doi/pdf/10.1145/3531130.3533333 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.pages | 11:1-13 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | linear equations |
| dc.subject.en | sets with atoms |
| dc.subject.en | orbit-finite sets |
| dc.title | Solvability of orbit-finite systems of linear equations |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |