COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Senescent Ground Tree Rewrite Systems

## Senescent Ground Tree Rewrite SystemsAdd to your list(s) Download to your calendar using vCal - Matthew Hague, Royal Holloway
- Friday 21 November 2014, 16:00-17:00
- Room FW26, Computer Laboratory, William Gates Building.
If you have a question about this talk, please contact Jonathan Hayman. Ground Tree Rewrite Systems with State provide a model of tree-manipulating programs and may be used as an abstraction of first-order recursive programs with dynamic thread creation. Unfortunately such systems are known to have an undecidable control state reachability problem. The same undecidability holds also for two-threaded recursive programs, leading to the study of under-approximation techniques such as context-bounding, and, more recently, scope-bounding. In this talk we will look at the transfer of these under-approximations to ground tree rewrite systems with state, in particular leading to the introduction of Senescent Ground Tree Rewrite Systems. Senescent ground tree rewrite systems are a restriction of ground tree rewrite systems with state such that nodes of the tree may no longer be rewritten after having witnessed an a priori fixed number of control state changes. That is, the tree is subject to the effects of aging where the passage of time is marked by the control state. As well as generalising scope-bounded multi-stack pushdown systems, we show – via reductions to and from reset Petri-nets – that these systems have an Ackermann-complete control state reachability problem. However, reachability of a regular set of trees remains undecidable. This work was presented at CSL -LICS 2014. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Cambridge talks
- Computer Laboratory talks
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Room FW26, Computer Laboratory, William Gates Building
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other liststo be confirmed Centre of African Studies Occasional Talks DAK Seminars## Other talksCentriole Duplication: from body coordination in flies to skin cell biology and cancer Optimising fresh produce quality monitoring and analysis Cambridge - Corporate Finance Theory Symposium September 2018 - Day 1 Recent Changes of Korean Government's Strategy on back-end fuel cycle and the changing course of a University Laboratory Statistical Methods in Pre- and Clinical Drug Development: Tumour Growth-Inhibition Model Example |