We prove a tight log n lower bound on middle space for one-way alternating Turing machines that accept nonregular tally languages. This is to be compared with the optimal log log n lower bound in the literature for nonregular languages over arbitrary alphabets.
A remark on middle space bounded alternating Turing machines / C. Mereghetti, G. Pighizzini. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 56:4(1995), pp. 229-232. [10.1016/0020-0190(95)00151-2]
A remark on middle space bounded alternating Turing machines
C. Mereghetti
;G. PighizziniUltimo
1995
Abstract
We prove a tight log n lower bound on middle space for one-way alternating Turing machines that accept nonregular tally languages. This is to be compared with the optimal log log n lower bound in the literature for nonregular languages over arbitrary alphabets.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
320.4 kB
Formato
Adobe PDF
|
320.4 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.
