Analysis of functions with a finite number of return values

Paul Zimmermann 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : A class of functions with a finite number of return values is defined over combinatorial structures. We prove that the characterization of combinatorial structures by such a function is equivalent to a set of grammar productions and we show how to derive these productions from the body of the function. In the field of automatic average case analysis, this result allows the use of functions, which makes the description of algorithms more natural and smaller
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00074936
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 5:00:44 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:24:58 PM

Identifiers

  • HAL Id : inria-00074936, version 1

Collections

Citation

Paul Zimmermann. Analysis of functions with a finite number of return values. [Research Report] RR-1625, INRIA. 1992. ⟨inria-00074936⟩

Share

Metrics

Record views

146

Files downloads

109