Constrained Dynamic Tree Networks

Matthew Hague, Vincent Penelle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

39 Downloads (Pure)


We generalise Constrained Dynamic Pushdown Networks, introduced by Bouajjani et al, to Constrained Dynamic Tree Networks. In this model, we have trees of processes which may monitor their children. We allow the processes to be defined by any computation model for which the alternating reachability problem is decidable. We address the problem of symbolic reachability analysis for this model. More precisely, we consider the problem of computing an effective representation of their reachability sets using finite state automata. We show that backwards reachability sets starting from regular sets of configurations are always regular. We provide an algorithm for computing backwards reachability sets using tree automata.
Original languageEnglish
Title of host publication12th International Conference on Reachability Problems
PublisherSpringer International Publishing
Number of pages14
ISBN (Electronic)978-3-030-00250-3
ISBN (Print)978-3-030-00249-7
Publication statusPublished - 2018

Publication series

NameLecture Notes in Computer Science


  • Model-checking
  • Dynamic Networks
  • Concurrency
  • Pushdown Systems
  • Alternation
  • Higher-order
  • Collapsible Pushdown Systems

Cite this