On Reachability for Unidirectional Channel Systems Extended with Regular Tests
Autor: | Jancar Petr, Prateek Karandikar, Philippe Schnoebelen |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2015 |
Předmět: | |
Zdroj: | Logical Methods in Computer Science, Vol Volume 11, Issue 2 (2015) |
Druh dokumentu: | article |
ISSN: | 1860-5974 |
DOI: | 10.2168/LMCS-11(2:2)2015 |
Popis: | "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. |
Databáze: | Directory of Open Access Journals |
Externí odkaz: |
načítá se...