Standard
On computational universality in language equations. / Okhotin, R. Alexander.
Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers. ed. / Maurice Margenstern. Vol. 3354 2005. p. 292-303 (Lecture Notes in Computer Science).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Okhotin, RA 2005,
On computational universality in language equations. in M Margenstern (ed.),
Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers. vol. 3354, Lecture Notes in Computer Science, pp. 292-303, 4th International Conference on Machines, Computations, and Universality, MCU 2004, Saint Petersburg, Russian Federation,
21/09/04.
https://doi.org/10.1007/978-3-540-31834-7_24
APA
Okhotin, R. A. (2005).
On computational universality in language equations. In M. Margenstern (Ed.),
Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers (Vol. 3354, pp. 292-303). (Lecture Notes in Computer Science).
https://doi.org/10.1007/978-3-540-31834-7_24
Vancouver
Okhotin RA.
On computational universality in language equations. In Margenstern M, editor, Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers. Vol. 3354. 2005. p. 292-303. (Lecture Notes in Computer Science).
https://doi.org/10.1007/978-3-540-31834-7_24
Author
Okhotin, R. Alexander. /
On computational universality in language equations. Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers. editor / Maurice Margenstern. Vol. 3354 2005. pp. 292-303 (Lecture Notes in Computer Science).
BibTeX
@inproceedings{41bab97ae74f475290cfcedfdc8dd83b,
title = "On computational universality in language equations",
abstract = "It has recently been shown that several computational models - 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 shown that resolved systems with two variables and two equations are as expressive as more complicated systems, while one-variable equations are {"}almost{"} as expressive. Additionally, language equations with added quotient with regular languages are shown to be able to denote every arithmetical set.",
author = "Okhotin, {R. Alexander}",
year = "2005",
doi = "10.1007/978-3-540-31834-7_24",
language = "English",
volume = "3354",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "292--303",
editor = "Maurice Margenstern",
booktitle = "Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers",
note = "4th International Conference on Machines, Computations, and Universality, MCU 2004 ; Conference date: 21-09-2004 Through 24-09-2004",
}
RIS
TY - GEN
T1 - On computational universality in language equations
AU - Okhotin, R. Alexander
PY - 2005
Y1 - 2005
N2 - It has recently been shown that several computational models - 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 shown that resolved systems with two variables and two equations are as expressive as more complicated systems, while one-variable equations are "almost" as expressive. Additionally, language equations with added quotient with regular languages are shown to be able to denote every arithmetical set.
AB - It has recently been shown that several computational models - 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 shown that resolved systems with two variables and two equations are as expressive as more complicated systems, while one-variable equations are "almost" as expressive. Additionally, language equations with added quotient with regular languages are shown to be able to denote every arithmetical set.
UR - http://www.scopus.com/inward/record.url?scp=24144451092&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-31834-7_24
DO - 10.1007/978-3-540-31834-7_24
M3 - Conference contribution
AN - SCOPUS:24144451092
VL - 3354
T3 - Lecture Notes in Computer Science
SP - 292
EP - 303
BT - Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers
A2 - Margenstern, Maurice
T2 - 4th International Conference on Machines, Computations, and Universality, MCU 2004
Y2 - 21 September 2004 through 24 September 2004
ER -
