DOI

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.

Язык оригиналаанглийский
Название основной публикацииMachines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers
РедакторыMaurice Margenstern
Страницы292-303
Число страниц12
Том3354
DOI
СостояниеОпубликовано - 2005
Опубликовано для внешнего пользованияДа
Событие4th International Conference on Machines, Computations, and Universality, MCU 2004 - Saint Petersburg, Российская Федерация
Продолжительность: 21 сен 200424 сен 2004

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

НазваниеLecture Notes in Computer Science
ИздательSpringer Nature
ISSN (печатное издание)0302-9743

конференция

конференция4th International Conference on Machines, Computations, and Universality, MCU 2004
Страна/TерриторияРоссийская Федерация
ГородSaint Petersburg
Период21/09/0424/09/04

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 78926142