1 Search Results for "Keskin, Eren"

Document
DOI: 10.4230/LIPIcs.CONCUR.2023.8
Separability and Non-Determinizability of WSTS

Authors: Eren Keskin and Roland Meyer

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
There is a recent separability result for the languages of well-structured transition systems (WSTS) that is surprisingly general: disjoint WSTS languages are always separated by a regular language. The result assumes that one of the languages is accepted by a deterministic WSTS, and it is not known whether this assumption is needed. There are two ways to get rid of the assumption, none of which has led to conclusions so far: (i) show that WSTS can be determinized or (ii) generalize the separability result to non-deterministic WSTS languages. Our contribution is to show that (i) does not work but (ii) does. As for (i), we give a non-deterministic WSTS language that we prove cannot be accepted by a deterministic WSTS. The proof relies on a novel characterization of the languages accepted by deterministic WSTS. As for (ii), we show how to find finitely represented inductive invariants without having the tool of ideal decompositions at hand. Instead, we work with closures under converging sequences. Our results hold for upward- and downward-compatible WSTS.
Cite as

Eren Keskin and Roland Meyer. Separability and Non-Determinizability of WSTS. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 8:1-8:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keskin_et_al:LIPIcs.CONCUR.2023.8,
  author =	{Keskin, Eren and Meyer, Roland},
  title =	{{Separability and Non-Determinizability of WSTS}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.8},
  URN =		{urn:nbn:de:0030-drops-190025},
  doi =		{10.4230/LIPIcs.CONCUR.2023.8},
  annote =	{Keywords: WSTS, regular separability, determinization}
}
  • Refine by Author
  • 1 Keskin, Eren
  • 1 Meyer, Roland

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 WSTS
  • 1 determinization
  • 1 regular separability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact