On equations over sets of integers › SPbU Researchers Portal

Standard

On equations over sets of integers. / Jez, Artur; Okhotin, Alexander.

STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. 2010. p. 477-488 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 5).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Jez, A & Okhotin, A 2010, On equations over sets of integers. in STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, LIPIcs, vol. 5, pp. 477-488, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, 4/03/10. https://doi.org/10.4230/LIPIcs.STACS.2010.2478

APA

Jez, A., & Okhotin, A. (2010). On equations over sets of integers. In STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science (pp. 477-488). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 5). https://doi.org/10.4230/LIPIcs.STACS.2010.2478

Vancouver

Jez A, Okhotin A. On equations over sets of integers. In STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. 2010. p. 477-488. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.STACS.2010.2478

Author

Jez, Artur ; Okhotin, Alexander. / On equations over sets of integers. STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science. 2010. pp. 477-488 (Leibniz International Proceedings in Informatics, LIPIcs).

BibTeX

@inproceedings{4cbc8f36fdc94c29806f5e2107eb906b,

title = "On equations over sets of integers",

abstract = "Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition S + T = {m + n | m ∈ S, n ∈ T} and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction S - T = {m-n|m ∈ S,n ∈T,m≥ n}. Testing whether a given system has a solution is Σ1 1-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.",

keywords = "Arithmetical hierarchy, Computability, Hyper-arithmetical hierarchy, Language equations",

author = "Artur Jez and Alexander Okhotin",

year = "2010",

doi = "10.4230/LIPIcs.STACS.2010.2478",

language = "English",

isbn = "9783939897163",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

pages = "477--488",

booktitle = "STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science",

note = "27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 ; Conference date: 04-03-2010 Through 06-03-2010",

}

RIS

TY - GEN

T1 - On equations over sets of integers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2010

Y1 - 2010

N2 - Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition S + T = {m + n | m ∈ S, n ∈ T} and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction S - T = {m-n|m ∈ S,n ∈T,m≥ n}. Testing whether a given system has a solution is Σ1 1-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.

AB - Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition S + T = {m + n | m ∈ S, n ∈ T} and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction S - T = {m-n|m ∈ S,n ∈T,m≥ n}. Testing whether a given system has a solution is Σ1 1-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.

KW - Arithmetical hierarchy

KW - Computability

KW - Hyper-arithmetical hierarchy

KW - Language equations

UR - http://www.scopus.com/inward/record.url?scp=84880277687&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.STACS.2010.2478

DO - 10.4230/LIPIcs.STACS.2010.2478

M3 - Conference contribution

AN - SCOPUS:84880277687

SN - 9783939897163

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 477

EP - 488

BT - STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science

T2 - 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010

Y2 - 4 March 2010 through 6 March 2010

ER -

ID: 78935862