1 Search Results for "Abu Nassar, Antonio"

Document
DOI: 10.4230/LIPIcs.CSL.2022.3
Simulation by Rounds of Letter-To-Letter Transducers

Authors: Antonio Abu Nassar and Shaull Almagor

Published in: LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022)

Abstract
Letter-to-letter transducers are a standard formalism for modeling reactive systems. Often, two transducers that model similar systems differ locally from one another, by behaving similarly, up to permutations of the input and output letters within "rounds". In this work, we introduce and study notions of simulation by rounds and equivalence by rounds of transducers. In our setting, words are partitioned to consecutive subwords of a fixed length k, called rounds. Then, a transducer 𝒯₁ is k-round simulated by transducer 𝒯₂ if, intuitively, for every input word x, we can permute the letters within each round in x, such that the output of 𝒯₂ on the permuted word is itself a permutation of the output of 𝒯₁ on x. Finally, two transducers are k-round equivalent if they simulate each other. We solve two main decision problems, namely whether 𝒯₂ k-round simulates 𝒯₁ (1) when k is given as input, and (2) for an existentially quantified k. We demonstrate the usefulness of the definitions by applying them to process symmetry: a setting in which a permutation in the identities of processes in a multi-process system naturally gives rise to two transducers, whose k-round equivalence corresponds to stability against such permutations.
Cite as

Antonio Abu Nassar and Shaull Almagor. Simulation by Rounds of Letter-To-Letter Transducers. In 30th EACSL Annual Conference on Computer Science Logic (CSL 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 216, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abunassar_et_al:LIPIcs.CSL.2022.3,
  author =	{Abu Nassar, Antonio and Almagor, Shaull},
  title =	{{Simulation by Rounds of Letter-To-Letter Transducers}},
  booktitle =	{30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-218-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{216},
  editor =	{Manea, Florin and Simpson, Alex},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.3},
  URN =		{urn:nbn:de:0030-drops-157231},
  doi =		{10.4230/LIPIcs.CSL.2022.3},
  annote =	{Keywords: Transducers, Permutations, Parikh, Simulation, Equivalence}
}
  • Refine by Author
  • 1 Abu Nassar, Antonio
  • 1 Almagor, Shaull

  • Refine by Classification
  • 1 Theory of computation → Abstraction
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Verification by model checking

  • Refine by Keyword
  • 1 Equivalence
  • 1 Parikh
  • 1 Permutations
  • 1 Simulation
  • 1 Transducers

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact