On Reachability for Unidirectional Channel Systems Extended with Regular Tests
"Unidirectional channel systems" (Chambart & Schnoebelen, CONCUR 2008) are finite-state systems where one-way communication from a Sender to a Receiver goes via one reliable and one unreliable unbounded fifo channel. While reachability is decidable for these systems, equipping them wit...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2015-04-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/876/pdf |
| Summary: | "Unidirectional channel systems" (Chambart & Schnoebelen, CONCUR 2008) are
finite-state systems where one-way communication from a Sender to a Receiver
goes via one reliable and one unreliable unbounded fifo channel. While
reachability is decidable for these systems, equipping them with the
possibility of testing regular properties on the contents of channels makes it
undecidable. Decidability is preserved when only emptiness and nonemptiness
tests are considered: the proof relies on an elaborate reduction to a
generalized version of Post's Embedding Problem. |
|---|---|
| ISSN: | 1860-5974 |