Space Complexity of Stack Automata Models

DOI10.1142/S0129054121420090zbMATH Open1518.68178arXiv2212.00891OpenAlexW3199131588MaRDI QIDQ6169902FDOQ6169902

Oscar H. Ibarra, Luca Prigioniero, Ian McQuillan, Jozef jun. Jirásek

Publication date: 15 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2212.00891

Recommendations

• Space complexity of stack automata models
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• Generalizations of checking stack automata: characterizations and hierarchies
• Variations of checking stack automata: obtaining unexpected decidability properties
• Alternating Pushdown and Stack Automata

zbMATH Keywords

pushdown automataspace complexitystack automatachecking stack automatamachine models

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Visibly pushdown languages
• Title not available (Why is that?)
• Pushdown automata and constant height: decidability and bounds
• Mathematical Foundations of Computer Science 2005
• Title not available (Why is that?)
• Checking automata and one-way stack languages
• The power of two-way deterministic checking stack automata
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• Stack languages and log n space
• Sets accepted by one-way stack automata are context sensitive
• On store languages of language acceptors
• Deterministic Stack Transducers

Cited In (5)

• Tree-walking-storage automata
• On dynamics of automata with a stack
• Iterated stack automata and complexity classes
• Visit-bounded stack automata
• Space-time trade-offs for stack-based algorithms

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)