Standard

Computational universality in one-variable language equations. / Okhotin, Alexander.

In: Fundamenta Informaticae, Vol. 74, No. 4, 21.12.2006, p. 563-578.

Research output: Contribution to journal › Article › peer-review

Harvard

Okhotin, A 2006, 'Computational universality in one-variable language equations', Fundamenta Informaticae, vol. 74, no. 4, pp. 563-578.

APA

Okhotin, A. (2006). Computational universality in one-variable language equations. Fundamenta Informaticae, 74(4), 563-578.

Vancouver

Okhotin A. Computational universality in one-variable language equations. Fundamenta Informaticae. 2006 Dec 21;74(4):563-578.

Author

Okhotin, Alexander. / Computational universality in one-variable language equations. In: Fundamenta Informaticae. 2006 ; Vol. 74, No. 4. pp. 563-578.

BibTeX

@article{5eb91f009b7c40019f7521da7cebd501,
title = "Computational universality in one-variable language equations",
abstract = "It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic.",
author = "Alexander Okhotin",
year = "2006",
month = dec,
day = "21",
language = "English",
volume = "74",
pages = "563--578",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "4",

}

RIS

TY - JOUR

T1 - Computational universality in one-variable language equations

AU - Okhotin, Alexander

PY - 2006/12/21

Y1 - 2006/12/21

N2 - It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic.

AB - It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic.

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

M3 - Article

AN - SCOPUS:33845537474

VL - 74

SP - 563

EP - 578

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -

ID: 41141358