Program size complexity of correction grammars in the ershov hierarchy

John Case, James S. Royer

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

1 Scopus citations

Abstract

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 Δ02. Herein we study the relative succinctness between these classes of correction grammars. Example: Given u and v, transfinite elements of O with u <o v (Kleene’s ordering on O), for each Ø(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
EditorsNataša Jonoska, Laurent Bienvenu, Arnold Beckmann
PublisherSpringer Verlag
Pages240-250
Number of pages11
ISBN (Print)9783319401881
DOIs
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)
Volume9709
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th Conference on Computability in Europe, CiE 2016
Country/TerritoryFrance
CityParis
Period6/27/167/1/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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