A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS
Tekijät: Lehtinen T, Okhotin A
Kustantaja: WORLD SCIENTIFIC PUBL CO PTE LTD
Julkaisuvuosi: 2011
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Lehden akronyymi: INT J FOUND COMPUT S
Numero sarjassa: 2
Vuosikerta: 22
Numero: 2
Aloitussivu: 377
Lopetussivu: 393
Sivujen määrä: 17
ISSN: 0129-0541
DOI: https://doi.org/10.1142/S012905411100809X
Tiivistelmä
Systems of equations of the form X = Y + Z and X C, in which the unknowns sets of natural numbers, "+" denotes elementwise sum of sets S + T = {m + n vertical bar m is an element of S, n is an element of T}, and C is an ultimately periodic constant, have recently been proved to be computationally universal (Jet, Okhotin, "Equations over sets of natural numbers with addition only", STACS 2009). This paper establishes some limitations of such systems. A class of sets of numbers that cannot be represented by unique, least or greatest solutions of systems of this form is defined, and a particular set in this class is constructed. The argument is then extended to equations over sets of integers.
Systems of equations of the form X = Y + Z and X C, in which the unknowns sets of natural numbers, "+" denotes elementwise sum of sets S + T = {m + n vertical bar m is an element of S, n is an element of T}, and C is an ultimately periodic constant, have recently been proved to be computationally universal (Jet, Okhotin, "Equations over sets of natural numbers with addition only", STACS 2009). This paper establishes some limitations of such systems. A class of sets of numbers that cannot be represented by unique, least or greatest solutions of systems of this form is defined, and a particular set in this class is constructed. The argument is then extended to equations over sets of integers.
Turun yliopiston Tutkimustietojärjestelmän portaali