Minimal Size of Counters for (Real-Time) Multicounter Automata

DOI10.3233/FI-2021-2053OpenAlexW3198654765MaRDI QIDQ5158661

Zuzana Bednárová, Viliam Geffert

Publication date: 25 October 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2053

zbMATH Keywords

pushdown automataspace complexityreal-time automatacounter automata

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space bounds for processing contentless inputs
• Turing machines with sublogarithmic space
• Space hierarchy theorem revised.
• New Results on the Minimum Amount of Useful Space
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Alternation
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Sublogarithmic Bounds on Space and Reversals
• A hierarchy that does not collapse : alternations in low level space
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Two Families of Languages Related to ALGOL
• Some Results on Tape-Bounded Turing Machines
• Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)

This page was built for publication: Minimal Size of Counters for (Real-Time) Multicounter Automata