Linear equations and recursively enumerable sets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909214823153664 |
|---|---|
| author | Honkala, Juha |
| author_facet | Honkala, Juha |
| contents | We study connections between linear equations over various semigroups and recursively enumerable sets of positive integers. We give variants of the universal Diophantine representation of recursively enumerable sets of positive integers established by Matiyasevich. These variants use linear equations with one unkwown instead of polynomial equations with several unknowns. As a corollary we get undecidability results for linear equations over morphism semigoups and over matrix semigroups. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_00688 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear equations and recursively enumerable sets Honkala, Juha Formal Languages and Automata Theory 68Q45 We study connections between linear equations over various semigroups and recursively enumerable sets of positive integers. We give variants of the universal Diophantine representation of recursively enumerable sets of positive integers established by Matiyasevich. These variants use linear equations with one unkwown instead of polynomial equations with several unknowns. As a corollary we get undecidability results for linear equations over morphism semigoups and over matrix semigroups. |
| title | Linear equations and recursively enumerable sets |
| topic | Formal Languages and Automata Theory 68Q45 |
| url | https://arxiv.org/abs/2406.00688 |