DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2024.36

Directed Regular and Context-Free Languages

Authors: Moses Ganardi, Irmak Sağlam, and Georg Zetzsche

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract

We study the problem of deciding whether a given language is directed. A language L is directed if every pair of words in L have a common (scattered) superword in L. Deciding directedness is a fundamental problem in connection with ideal decompositions of downward closed sets. Another motivation is that deciding whether two directed context-free languages have the same downward closures can be decided in polynomial time, whereas for general context-free languages, this problem is known to be coNEXP-complete. We show that the directedness problem for regular languages, given as NFAs, belongs to AC¹, and thus polynomial time. Moreover, it is NL-complete for fixed alphabet sizes. Furthermore, we show that for context-free languages, the directedness problem is PSPACE-complete.

Cite as

Moses Ganardi, Irmak Sağlam, and Georg Zetzsche. Directed Regular and Context-Free Languages. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.STACS.2024.36,
  author =	{Ganardi, Moses and Sa\u{g}lam, Irmak and Zetzsche, Georg},
  title =	{{Directed Regular and Context-Free Languages}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.36},
  URN =		{urn:nbn:de:0030-drops-197465},
  doi =		{10.4230/LIPIcs.STACS.2024.36},
  annote =	{Keywords: Subword, ideal, language, regular, context-free, equivalence, downward closure, compression}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.34

Solving Odd-Fair Parity Games

Authors: Irmak Sağlam and Anne-Kathrin Schmuck

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

This paper discusses the problem of efficiently solving parity games where player Odd has to obey an additional strong transition fairness constraint on its vertices - given that a player Odd vertex v is visited infinitely often, a particular subset of the outgoing edges (called live edges) of v has to be taken infinitely often. Such games, which we call Odd-fair parity games, naturally arise from abstractions of cyber-physical systems for planning and control. In this paper, we present a new Zielonka-type algorithm for solving Odd-fair parity games. This algorithm not only shares the same worst-case time complexity as Zielonka’s algorithm for (normal) parity games but also preserves the algorithmic advantage Zielonka’s algorithm possesses over other parity solvers with exponential time complexity. We additionally introduce a formalization of Odd player winning strategies in such games, which were unexplored previous to this work. This formalization serves dual purposes: firstly, it enables us to prove our Zielonka-type algorithm; secondly, it stands as a noteworthy contribution in its own right, augmenting our understanding of additional fairness assumptions in two-player games.

Cite as

Irmak Sağlam and Anne-Kathrin Schmuck. Solving Odd-Fair Parity Games. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 34:1-34:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saglam_et_al:LIPIcs.FSTTCS.2023.34,
  author =	{Sa\u{g}lam, Irmak and Schmuck, Anne-Kathrin},
  title =	{{Solving Odd-Fair Parity Games}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{34:1--34:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.34},
  URN =		{urn:nbn:de:0030-drops-194077},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.34},
  annote =	{Keywords: parity games, strong transition fairness, algorithmic game theory}
}

Search Results

Documents authored by Sağlam, Irmak

Directed Regular and Context-Free Languages

Abstract

Cite as

Solving Odd-Fair Parity Games

Abstract

Cite as

Thanks for your feedback!

Could not send message