### Abstract

A general correction grammar for a language L is a program g that, for each (x, t) ∈ N^{2}, 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 i_{v} for a finite (alternatively, a co-finite) set A such that the smallest u-correction grammar for A is >H(i_{v}). 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 language | English (US) |
---|---|

Title of host publication | Pursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Proceedings |

Publisher | Springer Verlag |

Pages | 240-250 |

Number of pages | 11 |

Volume | 9709 |

ISBN (Print) | 9783319401881 |

DOIs | |

State | Published - 2016 |

Event | 12th Conference on Computability in Europe, CiE 2016 - Paris, France Duration: Jun 27 2016 → Jul 1 2016 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 9709 |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 12th Conference on Computability in Europe, CiE 2016 |
---|---|

Country | France |

City | Paris |

Period | 6/27/16 → 7/1/16 |

### 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

*Pursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Proceedings*(Vol. 9709, pp. 240-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9709). Springer Verlag. https://doi.org/10.1007/978-3-319-40189-8_25