Iterative arrays (IAs) are a parallel computational model with a sequential processing of the input. They are one-dimensional arrays of interacting identical deterministic finite automata. In this paper, realtime-IAs with sublinear space bounds are used to recognize formal languages. The existence of an infinite proper hierarchy of space complexity classes between logarithmic and linear space bounds is proved. Some decidability questions on logarithmically space bounded realtime-IAs are investigated, and an optimal logarithmic space lower bound for non-regular language recognition on realtime-IAs is shown. Finally, some non-recursive trade-offs between space bounded realtime-IAs are emphasized.
Sublinearly space bounded iterative arrays / A. Malcher, C. Mereghetti, B.S. Palano. - In: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - ISSN 0129-0541. - 21:5(2010), pp. 853-858. ((Intervento presentato al 12. convegno International Conference on Automata and Formal Languages tenutosi a Balatonfured nel 2008.
Sublinearly space bounded iterative arrays
C. MereghettiSecondo
;B.S. PalanoUltimo
2010
Abstract
Iterative arrays (IAs) are a parallel computational model with a sequential processing of the input. They are one-dimensional arrays of interacting identical deterministic finite automata. In this paper, realtime-IAs with sublinear space bounds are used to recognize formal languages. The existence of an infinite proper hierarchy of space complexity classes between logarithmic and linear space bounds is proved. Some decidability questions on logarithmically space bounded realtime-IAs are investigated, and an optimal logarithmic space lower bound for non-regular language recognition on realtime-IAs is shown. Finally, some non-recursive trade-offs between space bounded realtime-IAs are emphasized.File | Dimensione | Formato | |
---|---|---|---|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
237.89 kB
Formato
Adobe PDF
|
237.89 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.