Equations over sets of integers with addition only |
| |
Affiliation: | 1. Institute of Computer Science, University of Wrocław, Poland;2. Department of Mathematics and Statistics, University of Turku, Finland |
| |
Abstract: | Systems of equations of the form and are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set there exists a system with a unique (least, greatest) solution containing a component T with . Testing solution existence for these equations is -complete, solution uniqueness is -complete, and finiteness of the set of solutions is -complete. A similar construction for integers represents any hyper-arithmetical set by a set satisfying , whereas testing solution existence is -complete. |
| |
Keywords: | Language equations Unary languages Concatenation Computability |
本文献已被 ScienceDirect 等数据库收录! |
|