Pushdown and one-counter automata: constant and non-constant memory usage

DOI10.1007/978-3-031-34326-1_11OpenAlexW4381895283MaRDI QIDQ6175096

Giovanni Pighizzini, Luca Prigioniero

Publication date: 17 August 2023

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-34326-1_11

zbMATH Keywords

pushdown automatadescriptional complexityone-counter automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• More concise representation of regular languages by automata and regular expressions
• New Results on the Minimum Amount of Useful Space
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Pumping and pushdown machines
• Pushdown automata and constant height: decidability and bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pushdown and one-counter automata: constant and non-constant memory usage