Space Complexity of Stack Automata Models

Abstract

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 computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves (up to small technicalities explained in the paper) like a linear function, or it grows arbitrarily larger than the length of the input word. However, this result does not hold for non-erasing stack automata; we provide an example when the space complexity grows with the square root of the input length. Furthermore, an investigation is done regarding the best complexity of any machine accepting a given language, and on decidability of space complexity properties.

Contributors

Nataša Jonoska: [e-mail]

Dmytro Savchuk: [e-mail]

Oscar H. Ibarra: [e-mail]

Jozef Jirásek Jr.: [e-mail]

Ian McQuillan: [e-mail]

Luca Prigioniero:

ORCID: http://orcid.org/0000-0001-7163-4965

[e-mail]

Journal

Journal ID (publisher-id): 978-3-030-48516-0

Journal ID (doi): 10.1007/978-3-030-48516-0

Journal ID (nlm-ta): Developments in Language Theory

Title: Developments in Language Theory

Subtitle: 24th International Conference, DLT 2020, Tampa, FL, USA, May 11–15, 2020, Proceedings

ISBN (Print): 978-3-030-48515-3

ISBN (Electronic): 978-3-030-48516-0

Publication date (Electronic): 26 May 2020

Volume: 12086

Pages: 137-149

Affiliations

[8 ]GRID grid.170693.a, ISNI 0000 0001 2353 285X, University of South Florida, ; Tampa, FL USA

[9 ]GRID grid.170693.a, ISNI 0000 0001 2353 285X, University of South Florida, ; Tampa, FL USA

[10 ]GRID grid.133342.4, ISNI 0000 0004 1936 9676, Department of Computer Science, , University of California, ; Santa Barbara, CA 93106 USA

[11 ]GRID grid.25152.31, ISNI 0000 0001 2154 235X, Department of Computer Science, , University of Saskatchewan, ; Saskatoon, SK S7N 5A9 Canada

[12 ]GRID grid.4708.b, ISNI 0000 0004 1757 2822, Dipartimento di Informatica, , Università degli Studi di Milano, ; Milan, Italy

Article

Publisher ID: 11

DOI: 10.1007/978-3-030-48516-0_11

PMC ID: 7247887

Copyright statement: © Springer Nature Switzerland AG 2020

License:

This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.

Categories

Subject: Article

Custom metadata

issue-copyright-statement © Springer Nature Switzerland AG 2020