On flat lossy channel machines
| Autor: | Schnoebelen, Philippe |
|---|---|
| Přispěvatelé: | Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), ANR-17-CE40-0028,BRAVAS,IDEAL-BASED ALGORITHMS FOR VASSES AND WELL-STRUCTURED SYSTEMS(2017) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
060201 languages & linguistics
FOS: Computer and information sciences Computer Science - Logic in Computer Science Automated verification Formal Languages and Automata Theory (cs.FL) Flat systems Lossy channels Computer Science - Formal Languages and Automata Theory 06 humanities and the arts 02 engineering and technology Data_CODINGANDINFORMATIONTHEORY Theory of computation → Logic and verification Logic in Computer Science (cs.LO) 0602 languages and literature 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Infinite state systems Computer Science::Formal Languages and Automata Theory ComputingMilieux_MISCELLANEOUS Computer Science::Information Theory |
| Zdroj: | 29th EACSL Conference on Computer Science Logic 29th EACSL Conference on Computer Science Logic, Jan 2021, Ljubljana, Slovenia. ⟨10.4230/LIPIcs.CSL.2021.37⟩ |
| DOI: | 10.4230/LIPIcs.CSL.2021.37⟩ |
| Popis: | 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. Comment: Submitted for publication |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|