On the Use of Inaccessible Numbers and Order Indiscernibles in Lower Bound Arguments for Random Access Machines
Maass, Wolfgang
J. Symbolic Logic, Tome 53 (1988) no. 1, p. 1098-1109 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We prove optimal lower bounds on the computation time for several well-known test problems on a quite realistic computational model: the random access machine. These lower bound arguments may be of special interest for logicians because they rely on finitary analogues of two important concepts from mathematical logic: inaccessible numbers and order indiscernibles.
Publié le : 1988-12-14
Classification:  
@article{1183742784,
     author = {Maass, Wolfgang},
     title = {On the Use of Inaccessible Numbers and Order Indiscernibles in Lower Bound Arguments for Random Access Machines},
     journal = {J. Symbolic Logic},
     volume = {53},
     number = {1},
     year = {1988},
     pages = { 1098-1109},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742784}
}

Maass, Wolfgang. On the Use of Inaccessible Numbers and Order Indiscernibles in Lower Bound Arguments for Random Access Machines. J. Symbolic Logic, Tome 53 (1988) no. 1, pp.  1098-1109. http://gdmltest.u-ga.fr/item/1183742784/