Cargando…

Space Complexity of Stack Automata Models

This paper examines several measures of space complexity on variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept any word in a language (weak measure), the maximum stack size used in any accepting computa...

Descripción completa

Detalles Bibliográficos
Autores principales: Ibarra, Oscar H., Jirásek, Jozef, McQuillan, Ian, Prigioniero, Luca
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247887/
http://dx.doi.org/10.1007/978-3-030-48516-0_11