Program size complexity of correction grammars in the ershov hierarchy

John Case, James S Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A general correction grammar for a language L is a program g that, for each (x, t) ∈ N2, issues a yes or no (where when t = 0, the answer is always no) which is g’s t-th approximation in answering “x∈L?”; moreover, g’s sequence of approximations for a given x is required to converge after finitely many mind-changes. The set of correction grammars can be transfinitely stratified based on O, Kleene’s system of notation for constructive ordinals. For u ∈ O, a u-correction grammar’s mind changes have to fit a count-down process from ordinal notation u; these u-correction grammars capture precisely the Σu −1 sets in Ershov’s hierarchy of sets for Δ0 2. Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with u (2)-computable H: N → N, there is a v-correction grammar iv for a finite (alternatively, a co-finite) set A such that the smallest u-correction grammar for A is >H(iv). We also exhibit relative succinctness progressions in these systems of grammars and study the “information-theoretic” underpinnings of relative succinctness. Along the way, we verify and improve slightly a 1972 conjecture of Meyer and Bagchi.

Original languageEnglish (US)
Title of host publicationPursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783319401881
StatePublished - 2016
Event12th Conference on Computability in Europe, CiE 2016 - Paris, France
Duration: Jun 27 2016Jul 1 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Other12th Conference on Computability in Europe, CiE 2016

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Program size complexity of correction grammars in the ershov hierarchy'. Together they form a unique fingerprint.

Cite this