Wojciech Czerwiński ; Sławomir Lasota - Regular Separability of One Counter Automata

lmcs:4417 - Logical Methods in Computer Science, June 11, 2019, Volume 15, Issue 2 - https://doi.org/10.23638/LMCS-15(2:20)2019
Regular Separability of One Counter AutomataArticle

Authors: Wojciech Czerwiński ORCID; Sławomir Lasota ORCID

The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other.
Our main result is decidability, and PSpace-completeness, of the regular separability problem for languages of one counter automata without zero tests (also known as one counter nets). This contrasts with undecidability of the regularity problem for one counter nets, and with undecidability of the regular separability problem for one counter automata, which is our second result.

https://doi.org/10.23638/LMCS-15(2:20)2019
Source: arXiv.org:1701.02808
Volume: Volume 15, Issue 2
Secondary volumes: Selected Papers of the 32nd ACM/IEEE Symposium on Logic in Computer Science (LICS 2017)
Published on: June 11, 2019
Accepted on: June 6, 2019
Submitted on: March 30, 2018
Keywords: Computer Science - Formal Languages and Automata Theory
Licence: Attribution 4.0 International (CC BY 4.0)
Funding:
    Source : OpenAIRE Graph
  • A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 3905 times.
This article's PDF has been downloaded 1129 times.