Regular Separability and Intersection Emptiness Are Independent Problems

Authors Ramanathan S. Thinniyam , Georg Zetzsche



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.51.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Ramanathan S. Thinniyam
  • Max Planck Institute for Software Systems (MPI-SWS), Germany
Georg Zetzsche
  • Max Planck Institute for Software Systems (MPI-SWS), Germany

Acknowledgements

We thank Lorenzo Clemente and Wojciech Czerwiński for fruitful discussions.

Cite AsGet BibTex

Ramanathan S. Thinniyam and Georg Zetzsche. Regular Separability and Intersection Emptiness Are Independent Problems. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.51

Abstract

The problem of regular separability asks, given two languages K and L, whether there exists a regular language S that includes K and is disjoint from L. This problem becomes interesting when the input languages K and L are drawn from language classes beyond the regular languages. For such classes, a mild and useful assumption is that they are full trios, i.e. closed under rational transductions. All the results on regular separability for full trios obtained so far exhibited a noteworthy correspondence with the intersection emptiness problem: In each case, regular separability is decidable if and only if intersection emptiness is decidable. This raises the question whether for full trios, regular separability can be reduced to intersection emptiness or vice-versa. We present counterexamples showing that neither of the two problems can be reduced to the other. More specifically, we describe full trios C_1, D_1, C_2, D_2 such that (i) intersection emptiness is decidable for C_1 and D_1, but regular separability is undecidable for C_1 and D_1 and (ii) regular separability is decidable for C_2 and D_2, but intersection emptiness is undecidable for C_2 and D_2.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Formal languages and automata theory
Keywords
  • Regular separability
  • intersection emptiness
  • decidability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Parosh Aziz Abdulla, Karlis Cerans, Bengt Jonsson, and Yih-Kuen Tsay. General decidability theorems for infinite-state systems. In Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, pages 313-321. IEEE, 1996. Google Scholar
  2. Jorge Almeida. Some algorithmic problems for pseudovarieties. Publ. Math. Debrecen, 54(1):531-552, 1999. Google Scholar
  3. Jean Berstel. Transductions and context-free languages. Springer-Verlag, 2013. Google Scholar
  4. Achim Blumensath and Erich Gradel. Automatic structures. In Proceedings of LICS 2000, pages 51-62. IEEE, 2000. Google Scholar
  5. Mikołaj Bojańczyk. It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton. Fundam. Inform., 154(1-4):37-46, 2017. Google Scholar
  6. Ahmed Bouajjani, Javier Esparza, and Tayssir Touili. A generic approach to the static analysis of concurrent programs with procedures. International Journal of Foundations of Computer Science, 14(04):551-582, 2003. Google Scholar
  7. Christian Choffrut and Serge Grigorieff. Separability of rational relations in A^*×ℕ^m by recognizable relations is decidable. Information processing letters, 99(1):27-32, 2006. Google Scholar
  8. Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, and Charles Paperman. Regular Separability of Parikh Automata. In Proceedings of ICALP 2017, pages 117:1-117:13, 2017. Google Scholar
  9. Lorenzo Clemente, Wojciech Czerwiński, Sławomir Lasota, and Charles Paperman. Separability of Reachability Sets of Vector Addition Systems. In Proceedings of STACS 2017, pages 24:1-24:14, 2017. Google Scholar
  10. Wojciech Czerwiński, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar, and Prakash Saivasan. Regular Separability of Well-Structured Transition Systems. In Proceedings of CONCUR 2018, pages 35:1-35:18, 2018. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2018.35.
  11. Wojciech Czerwiński, Wim Martens, Lorijn van Rooijen, Marc Zeitoun, and Georg Zetzsche. A Characterization for Decidable Separability by Piecewise Testable Languages. Discrete Mathematics & Theoretical Computer Science, 19(4), 2017. Google Scholar
  12. Wojciech Czerwiński and Georg Zetzsche. An Approach to Regular Separability in Vector Addition Systems, 2019. In preparation. Google Scholar
  13. Jürgen Dassow and Gheorghe Păun. Regulated Rewriting in Formal Language Theory. Springer, Heidelberg, 1989. Google Scholar
  14. Catherine Dufourd, Alain Finkel, and Philippe Schnoebelen. Reset Nets Between Decidability and Undecidability. In Proceedings of ICALP 1998, pages 103-115, 1998. Google Scholar
  15. Herbert B Enderton. A mathematical introduction to logic. Elsevier, 2001. Google Scholar
  16. Joost Engelfriet. Context-Free Grammars with Storage. CoRR, abs/1408.0683, 2014. URL: http://arxiv.org/abs/1408.0683.
  17. Alain Finkel and Philippe Schnoebelen. Fundamental Structures in Well-Structured Infinite Transition Systems. In Proceedings of LATIN 1998, pages 102-118, 1998. Google Scholar
  18. Gilles Geeraerts, Jean-François Raskin, and Laurent Van Begin. Well-structured languages. Acta Informatica, 44(3-4):249-288, 2007. Google Scholar
  19. Seymour Ginsburg and Sheila Greibach. Principal AFL. Journal of Computer and System Sciences, 4(4):308-338, 1970. Google Scholar
  20. Samuel J.v. Gool and Benjamin Steinberg. Pointlike sets for varieties determined by groups. Advances in Mathematics, 348:18-50, 2019. Google Scholar
  21. Jean Goubault-Larrecq and Sylvain Schmitz. Deciding Piecewise Testable Separability for Regular Tree Languages. In Proceedings of ICALP 2016, pages 97:1-97:15, 2016. Google Scholar
  22. Sheila A. Greibach. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7(3):311-324, 1978. Google Scholar
  23. Matthew Hague, Jonathan Kochems, and C.-H. Luke Ong. Unboundedness and Downward Closures of Higher-order Pushdown Automata. In POPL 2016, pages 151-163, New York, NY, USA, 2016. ACM. Google Scholar
  24. Juris Hartmanis. Context-free languages and Turing machine computations. In Proceedings of Symposia in Applied Mathematics, volume 19, pages 42-51, 1967. Google Scholar
  25. Harry B. Hunt III. On the Decidability of Grammar Problems. Journal of the ACM, 29(2):429-447, 1982. URL: https://doi.org/10.1145/322307.322317.
  26. Bakhadyr Khoussainov and Anil Nerode. Automatic presentations of structures. In Logic and Computational Complexity, volume 960 of LNCS, pages 367-392, Berlin, Heidelberg, 1995. Springer. Google Scholar
  27. Felix Klaedtke and Harald Rueß. Monadic Second-Order Logics with Cardinalities. In Proceedings of ICALP 2003, volume 2719 of LNCS, pages 681-696, Springer, Heidelberg, 2003. Springer. Google Scholar
  28. Eryk Kopczyński. Invisible Pushdown Languages. In Proceedings of LICS 2016, pages 867-872, New York, NY, USA, 2016. ACM. Google Scholar
  29. Sławomir Lasota and Wojciech Czerwiński. Regular Separability of One Counter Automata. Logical Methods in Computer Science, 15, 2019. Extended version of LICS 2017 paper. Google Scholar
  30. Richard Mayr. Undecidable problems in unreliable computations. Theoretical Computer Science, 297(1-3):337-354, 2003. Google Scholar
  31. Rohit J Parikh. On context-free languages. Journal of the ACM, 13(4):570-581, 1966. Google Scholar
  32. Thomas Place. Separating Regular Languages with Two Quantifiers Alternations. In Proceedings of LICS 2015, pages 202-213, 2015. Google Scholar
  33. Thomas Place, Lorijn van Rooijen, and Marc Zeitoun. Separating Regular Languages by Piecewise Testable and Unambiguous Languages. In Proceedings of MFCS 2013, pages 729-740, 2013. Google Scholar
  34. Thomas Place and Marc Zeitoun. Separation and the Successor Relation. In Proceedings of STACS 2015, pages 662-675, 2015. Google Scholar
  35. Thomas Place and Marc Zeitoun. Separating Regular Languages with First-Order Logic. Logical Methods in Computer Science, 12(1), 2016. Google Scholar
  36. Thomas Place and Marc Zeitoun. Concatenation Hierarchies: New Bottle, Old Wine. In Proceedings of CSR 2017, pages 25-37, 2017. Google Scholar
  37. Thomas Place and Marc Zeitoun. Separation for dot-depth two. In Proceedings of LICS 2017, pages 1-12, 2017. Google Scholar
  38. Thomas Place and Marc Zeitoun. The Covering Problem. Logical Methods in Computer Science, 14(3), 2018. Google Scholar
  39. Thomas G. Szymanski and John H. Williams. Noncanonical extensions of bottom-up parsing techniques. SIAM Journal on Computing, 5(2), 1976. Google Scholar
  40. Ramanathan S Thinniyam and Georg Zetzsche. Regular Separability and Intersection Emptiness are Independent Problems. arXiv preprint, 2019. URL: http://arxiv.org/abs/1908.04038.
  41. Georg Zetzsche. An Approach to Computing Downward Closures. In Proceedings of ICALP 2015, pages 440-451, 2015. Google Scholar
  42. Georg Zetzsche. Separability by piecewise testable languages and downward closures beyond subwords. In Proceedings of LICS 2018, pages 929-938, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail