Equations over sets of natural numbers with addition only

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

15 Цитирования (Scopus)

Аннотация

Systems of equations of the form X = YZ and X = C are considered, in which the unknowns are sets of natural numbers, "+" denotes pairwise sum of sets S + T = {m + n | m ∈ S, n ∈ T}, and C is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) setS⊆ ℕ there exists a system with a unique (least, greatest) solution containing a component T with S = {n | 16n + 13 ∈ T}. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.

Язык оригиналаанглийский
Название основной публикацииSTACS 2009 - 26th International Symposium on Theoretical Aspects of Computer Science
Страницы577-588
Число страниц12
СостояниеОпубликовано - 1 дек 2009
Событие26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 - Freiburg, Германия
Продолжительность: 26 фев 200928 фев 2009

Серия публикаций

НазваниеLeibniz International Proceedings in Informatics, LIPIcs
Том3
ISSN (печатное издание)1868-8969

конференция

конференция26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009
СтранаГермания
ГородFreiburg
Период26/02/0928/02/09

Предметные области Scopus

  • Программный продукт

Цитировать