On the ω-language Expressive Power of Extended Petri Nets |
| |
Authors: | A Finkel G Geeraerts J-F Raskin L Van Begin |
| |
Affiliation: | †L.S.V., École Normale Supérieure de Cachan – 61, av. du Président Wilson, 94235 CACHAN, Cedex, France;‡D.I., Université Libre de Bruxelles – bld. du Triomphe, 1050 Bruxelles, Belgium |
| |
Abstract: | In this paper, we study the expressive power of several monotonic extensions of Petri nets. We compare the expressive power of Petri nets, Petri nets extended with non-blocking arcs and Petri nets extended with transfer arcs, in terms of ω-languages. We show that the hierarchy of expressive powers of those models is strict. To prove these results, we propose original techniques that rely on well-quasi orderings and monotonicity properties. |
| |
Keywords: | (extended) Petri nets ω -languages |
本文献已被 ScienceDirect 等数据库收录! |
|