Petr, Jancar and Karandikar, Prateek and Schnoebelen, Philippe - On Reachability for Unidirectional Channel Systems Extended with Regular Tests

lmcs:876 - Logical Methods in Computer Science, April 17, 2015, Volume 11, Issue 2
On Reachability for Unidirectional Channel Systems Extended with Regular Tests

Authors: Petr, Jancar and Karandikar, Prateek and Schnoebelen, Philippe

"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.


Source : oai:arXiv.org:1406.5067
DOI : 10.2168/LMCS-11(2:2)2015
Volume: Volume 11, Issue 2
Published on: April 17, 2015
Submitted on: March 24, 2014
Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 168 times.
This article's PDF has been downloaded 63 times.