Paper: The Ordinal Recursive Complexity of Lossy Channel Systems (at LICS 2008)

Authors: Pierre Chambart Philippe Schnoebelen

Abstract

We show that reachability and termination for lossy channel systems is exactly at level F_omega^omega in the Fast-Growing Hierarchy of recursive functions, the first level that dominates all multiply-recursive functions.

BibTeX

  @InProceedings{ChambartSchnoebelen-TheOrdinalRecursive,
    author = 	 {Pierre Chambart and Philippe Schnoebelen},
    title = 	 {The Ordinal Recursive Complexity of Lossy Channel Systems},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {205--216},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }