Reference : On the concrete complexity of the successor function
Scientific congresses and symposiums : Unpublished conference
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
On the concrete complexity of the successor function
Berthé, Valérie []
Frougny, Christiane []
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Sakarovitch, Jacques []
Journées montoises d'informatique théorique
from 11-9-2012 to 14-9-2012
R. Jungers
[en] successor ; regular language ; transducer ; carry propagation ; complexity
[en] We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n integers (or more generally on the first n elements in a given language). This leads to the notion of amortized (or average) carry propagation when applying the successor function. The second question is a computational issue: estimating the number of operations (in classical terms of Turing machines complexity) required to compute the representations of the first n integers from the first one by applying n times the successor function. This leads to the notion of (amortized) complexity, i.e., the average amount of computations required to obtain the successor of an element.

File(s) associated to this reference

Fulltext file(s):

Open access
abstractJM.pdfAuthor postprint100.01 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
Rigo.pdfslides of the presentation833.92 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.