On flat lossy channel machines

2020/07/10 by Schnoebelen, Philippe · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2007.05269

Abstract

We show that reachability, repeated reachability, nontermination and unboundedness are NP-complete for Lossy Channel Machines that are flat, i.e., with no nested cycles in the control graph. The upper complexity bound relies on a fine analysis of iterations of lossy channel actions and uses compressed word techniques for efficiently reasoning with paths of exponential lengths. The lower bounds already apply to acyclic or single-path machines.

Cited by

• Fixed Parameter Tractable Linearizability Monitoring for Stack, Queue and Anagram Agnostic Data Types

Related

• Flat counter automata almost everywhere!
• The Complexity of Reachability Problems for Flat Counter Machines with Periodic Loops
• Taming Past LTL and Flat Counter Systems
• Computability of the Zero-Error Capacity of Noisy Channels
• Rice-like complexity lower bounds for Boolean and uniform automata networks