Abstract: This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (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 like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata; we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties.
Recommendations
Cites work
- Checking automata and one-way stack languages
- Deterministic stack transducers
- Generalizations of Checking Stack Automata: Characterizations and Hierarchies
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 5593330 (Why is no real title available?)
- scientific article; zbMATH DE number 3302285 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2005
- On store languages of language acceptors
- Pushdown automata and constant height: decidability and bounds
- Sets accepted by one-way stack automata are context sensitive
- Stack languages and log n space
- The power of two-way deterministic checking stack automata
- Visibly pushdown languages
Cited in
(10)- Iterated stack automata and complexity classes
- Space-time trade-offs for stack-based algorithms
- Space complexity of stack automata models
- On dynamics of automata with a stack
- Visit-bounded stack automata
- Tree-walking-storage automata
- Deterministic tree-walking-storage automata
- Deterministic real-time tree-walking-storage automata
- Deterministic real-time tree-walking-storage automata
- Tradeoff lower lounds for stack machines
This page was built for publication: Space Complexity of Stack Automata Models
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169902)
