HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Unfolding of finite concurrent automata

Abstract : We consider recognizable trace rewriting systems with level-regular contexts (RTL). A trace language is level-regular if the set of Foata normal forms of its elements is regular. We prove that the rewriting graph of a RTL is word-automatic. Thus its first-order theory is decidable. Then, we prove that the concurrent unfolding of a finite concurrent automaton with the reachability relation is a RTL graph. It follows that the first-order theory with the reachability predicate (FO[Reach] theory) of such an unfolding is decidable. It is known that this property holds also for the ground term rewriting graphs. We provide examples of finite concurrent automata of which the concurrent unfoldings fail to be ground term rewriting graphs. The infinite grid tree (for each vertex of an infinite grid, there is an edge from this vertex to the origin of a copy of the infinite grid) is such an unfolding. We prove that the infinite grid tree is not a ground term rewriting graph. We have thus obtained a new class of graphs for with a decidable FO[Reach] theory.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

Contributor : Alexandre Mansard Connect in order to contact the contributor
Submitted on : Thursday, April 19, 2018 - 5:40:25 PM
Last modification on : Wednesday, November 3, 2021 - 4:26:55 AM
Long-term archiving on: : Tuesday, September 18, 2018 - 3:54:51 PM


Files produced by the author(s)


  • HAL Id : hal-01771751, version 1



Alexandre Mansard. Unfolding of finite concurrent automata. 11th Interaction and Concurrency Experience, ICE 2018, Jun 2018, Madrid, Spain. pp.68-84. ⟨hal-01771751⟩



Record views


Files downloads