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 Automata

Authors: Wojciech Czerwiński ; Sławomir Lasota

    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.

    Volume: Volume 15, Issue 2
    Published on: June 11, 2019
    Accepted on: June 6, 2019
    Submitted on: March 30, 2018
    Keywords: Computer Science - Formal Languages and Automata Theory
      Source : OpenAIRE Graph
    • A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsCitedBy ARXIV 2005.09489
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.concur.2020.16
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2005.09489
    • 10.48550/arxiv.2005.09489
    • 10.4230/lipics.concur.2020.16
    • 2005.09489
    On the Separability Problem of String Constraints
    Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Dave, Vrunda ; Krishna, Shankara Narayanan ;

    Consultation statistics

    This page has been seen 923 times.
    This article's PDF has been downloaded 417 times.