Parameterised Pushdown Systems with Non-Atomic Writes

Details Parameterised Pushdown Systems with Non-Atomic Writes Parameterised Pushdown Systems with Non-Atomic Writes

2011-09-28

arxiv.org/abs/1109.6264v1

Computer Science

Formal Languages and Automata Theory

This is the long version of a paper appearing in FSTTCS 2011

Scientific paper

We consider the master/slave parameterised reachability problem for networks of pushdown systems, where communication is via a global store using only non-atomic reads and writes. We show that the control-state reachability problem is decidable. As part of the result, we provide a constructive extension of a theorem by Ehrenfeucht and Rozenberg to produce an NFA equivalent to certain kinds of CFG. Finally, we show that the non-parameterised version is undecidable.

Affiliated with

Also associated with

No associations

Rating

Parameterised Pushdown Systems with Non-Atomic Writes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Parameterised Pushdown Systems with Non-Atomic Writes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterised Pushdown Systems with Non-Atomic Writes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44106