Simulation by Rounds of Letter-to-Letter Transducers

DOI10.46298/LMCS-19(4:19)2023arXiv2105.01512MaRDI QIDQ6178697FDOQ6178697

Author name not available (Why is that?), Shaull Almagor

Publication date: 16 January 2024

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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 $mathcal{T}_1$ is $k$-round simulated by transducer $mathcal{T}_2$ if, intuitively, for every input word $x$, we can permute the letters within each round in $x$, such that the output of $mathcal{T}_2$ on the permuted word is itself a permutation of the output of $mathcal{T}_1$ on $x$. Finally, two transducers are $k$-round equivalent if they simulate each other. We solve two main decision problems, namely whether $mathcal{T}_2$ $k$-round simulates $mathcal{T}_1$ (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.

Full work available at URL: https://arxiv.org/abs/2105.01512

zbMATH Keywords

permutationssimulationequivalencetransducersParikh

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• On Context-Free Languages
• Characterizations of locally testable events
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Title not available (Why is that?)
• On NFAs where all states are final, initial, or both
• Fair simulation
• Handbook of Model Checking
• JUMPING FINITE AUTOMATA
• State complexity bounds for the commutative closure of group languages
• Jumping Finite Automata: Characterizations and Complexity
• Regular Symmetry Patterns
• Title not available (Why is that?)

This page was built for publication: Simulation by Rounds of Letter-to-Letter Transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178697)