Space Complexity of Stack Automata Models
| Autor: | Oscar H. Ibarra, Ian McQuillan, Jozef Jirásek, Luca Prigioniero |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
050101 languages & linguistics
Computer science Computation 05 social sciences Pushdown automaton 02 engineering and technology Measure (mathematics) Automaton Decidability Stack (abstract data type) Bounded function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Algorithm Computer Science::Formal Languages and Automata Theory Word (computer architecture) |
| Zdroj: | Developments in Language Theory ISBN: 9783030485153 DLT |
| DOI: | 10.1007/978-3-030-48516-0_11 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|