Solvability of orbit-finite systems of linear equations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909120522616832 |
|---|---|
| author | Ghosh, Arka Hofman, Piotr Lasota, Sławomir |
| author_facet | Ghosh, Arka Hofman, Piotr Lasota, Sławomir |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_09060 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Solvability of orbit-finite systems of linear equations Ghosh, Arka Hofman, Piotr Lasota, Sławomir Computation and Language Formal Languages and Automata Theory Logic in Computer Science 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 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. |
| title | Solvability of orbit-finite systems of linear equations |
| topic | Computation and Language Formal Languages and Automata Theory Logic in Computer Science |
| url | https://arxiv.org/abs/2201.09060 |