Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Jez, Artur
Okhotin, Alexander

dblp
dblp

Not MPG Author(s):

Okhotin, Alexander

BibTeX cite key*:

Jez2008ICALP

Title

Title*:

Computational completeness of equations over sets of natural numbers

Journal

Journal Title*:

Information and Computation

Journal's URL:

http://www.journals.elsevier.com/information-and-computation/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

Amsterdam

Publisher's
Address:

Amsterdam, The Netherlands

ISSN:

0890-5401

Vol, No, pp, Date

Volume*:

237

Number:


Publishing Date:

October 2014

Pages*:

56-94

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

Systems of finitely many equations of the form
$\varphi(X_1, \ldots, X_n)=\psi(X_1, \ldots, X_n)$
are considered,
in which the unknowns $X_i$
are sets of natural numbers,
while the expressions $\varphi,\psi$
may contain singleton constants
and the operations of union
and pairwise addition
$S+T=\{m+n \: : \: m \in S, \; n \in T\}$.
It is shown that the family of sets
representable by unique (least, greatest) solutions of such systems
is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers.
Basic decision problems for these systems
are located in the arithmetical hierarchy.
The same results are established for equations with addition and intersection.

URL for the Abstract:


Categories,
Keywords:

Language equations, Unary languages, Computability

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Jez2008ICALP,
AUTHOR = {Jez, Artur and Okhotin, Alexander},
TITLE = {Computational completeness of equations over sets of natural numbers},
JOURNAL = {Information and Computation},
PUBLISHER = {Elsevier},
YEAR = {2014},
VOLUME = {237},
PAGES = {56--94},
ADDRESS = {Amsterdam, The Netherlands},
MONTH = {October},
ISBN = {0890-5401},
}


Entry last modified by Artur Jez, 12/15/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
11/24/2014 06:21:05 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
11/24/2014 06:29:12 PM
11/24/2014 06:21:05 PM