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.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications, First International Computer Science Symposium in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, Proceedings
EditorsDima Grigoriev, John Harrison, Edward A. Hirsch
Pages292-303
Number of pages12
Volume3967 LNCS
DOIs
StatePublished - 2006
Externally publishedYes
Event1st International Computer Science Symposium in Russia, CSR 2006 - St. Petersburg, Russian Federation
Duration: 8 Jun 200612 Jun 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
ISSN (Print)0302-9743

Conference

Conference1st International Computer Science Symposium in Russia, CSR 2006
Country/TerritoryRussian Federation
CitySt. Petersburg
Period8/06/0612/06/06

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78926614