The complexity of regular abstractions of one-counter languages

DOI10.1145/2933575.2934561zbMath1401.68142arXiv1602.03419OpenAlexW2258615751MaRDI QIDQ4635876

Georg Zetzsche, K. Narayan Kumar, Prakash Saivasan, Piotr Hofman, Mohamed Faouzi Atig, Dmitry Chistikov

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Parikh imageone-counter automatadownward closureupward closure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Unnamed Item ⋮ Existential Definability over the Subword Ordering ⋮ Verifying quantitative temporal properties of procedural programs ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: The complexity of regular abstractions of one-counter languages