DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2023.39

Priority Downward Closures

Authors: Ashwani Anand and Georg Zetzsche

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

Abstract

When a system sends messages through a lossy channel, then the language encoding all sequences of messages can be abstracted by its downward closure, i.e. the set of all (not necessarily contiguous) subwords. This is useful because even if the system has infinitely many states, its downward closure is a regular language. However, if the channel has congestion control based on priorities assigned to the messages, then we need a finer abstraction: The downward closure with respect to the priority embedding. As for subword-based downward closures, one can also show that these priority downward closures are always regular. While computing finite automata for the subword-based downward closure is well understood, nothing is known in the case of priorities. We initiate the study of this problem and provide algorithms to compute priority downward closures for regular languages, one-counter languages, and context-free languages.

Cite as

Ashwani Anand and Georg Zetzsche. Priority Downward Closures. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.CONCUR.2023.39,
  author =	{Anand, Ashwani and Zetzsche, Georg},
  title =	{{Priority Downward Closures}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{39:1--39:18},
  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.39},
  URN =		{urn:nbn:de:0030-drops-190339},
  doi =		{10.4230/LIPIcs.CONCUR.2023.39},
  annote =	{Keywords: downward closure, priority order, pushdown automata, non-deterministic finite automata, abstraction, computability}
}

Search Results

Documents authored by Anand, Ashwani

Priority Downward Closures

Abstract

Cite as

Thanks for your feedback!

Could not send message