A NOTE ON LOGSPACE OPTIMIZATION

Authors
ALVAREZ C JENNER B
Citation
C. Alvarez et B. Jenner, A NOTE ON LOGSPACE OPTIMIZATION, Computational complexity, 5(2), 1995, pp. 155-166
Citations number
17
Categorie Soggetti
Mathematics, General","Computer Sciences",Mathematics,"Computer Science Theory & Methods
Journal title
Computational complexity → ACNP
ISSN journal
10163328
Volume
5
Issue
2
Year of publication
1995
Pages
155 - 166
Database
ISI
SICI code
1016-3328(1995)5:2<155:ANOLO>2.0.ZU;2-W
Abstract
We show that computing iterated multiplication of word matrices over { 0, 1}, using the operations maximum and concatenation, is complete fo r the class optL of logspace optimization functions. The same problem for word matrices over {1} is complete for the class FNL of nondeterm inistic logspace functions. Improving previously obtained results, we furthermore place the class optL in AC(1), and characterize FNL by res tricted logspace optimization functions.