DOI

Systems of language equations used by Ginsburg and Rice ("Two families of languages related to ALGOL", JACM, 1962) to represent context-free grammars are modified to use the symmetric difference operation instead of union. Contrary to a natural expectation that these two types of equations should have incomparable expressive power, it is shown that equations with symmetric difference can express every recursive set by their unique solutions, every recursively enumerable set by their least solutions and every co-recursively-enumerable set by their greatest solutions. The solution existence problem is II1-complete, the existence of a unique, a least or a greatest solution is ∏2-complete, while the existence of finitely many solutions is Σ3-complete.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings
РедакторыDima Grigoriev, John Harrison, Edward A. Hirsch
Страницы292-303
Число страниц12
Том3967 LNCS
DOI
СостояниеОпубликовано - 2006
Опубликовано для внешнего пользованияДа
Событие1st International Computer Science Symposium in Russia, CSR 2006 - St. Petersburg, Российская Федерация
Продолжительность: 8 июн 200612 июн 2006

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

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

конференция

конференция1st International Computer Science Symposium in Russia, CSR 2006
Страна/TерриторияРоссийская Федерация
ГородSt. Petersburg
Период8/06/0612/06/06

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

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

ID: 78926614