A Language-Based Comparison of Extensions of Petri Nets with and without Whole-Place Operations

被引：9
作者：
Abdulla, Parosh Aziz [1 ]
Delzanno, Giorgio [2 ]
Van Begin, Laurent [3 ]
机构：
[1] Uppsala Univ, Uppsala, Sweden
[2] Univ Genoa, Genoa, Italy
[3] Univ Libre Bruxelles, Brussels, Belgium
来源：
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS | 2009年 / 5457卷
关键词：
STRUCTURED TRANSITION-SYSTEMS; UNRELIABLE CHANNELS; EXPRESSIVE POWER; PERFECT;
D O I：
10.1007/978-3-642-00982-2_6
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We use language theory to study the relative expressiveness of in finite-state, models laying in between finite automata and Turing machines. We focus here our attention oil well structured transition systems that extend Petri nets. For these models. we study the impact of whole-place operations like transfers and resets on nets with indistinguishable tokens and with tokens that carry data over an infinite, domain. Our measure of expressiveness is defined in terms of the class of languages recognized by a given model using coverability of a configuration as accepting condition.
引用
收藏
页码：71 / +
页数：2
相关论文
共 14 条
  • [1] General decidability theorems for infinite-state systems
    Abdulla, PA
    Cerans, K
    Jonsson, B
    Tsay, YK
    [J]. 11TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1996, : 313 - 321
  • [2] Verifying programs with unreliable channels
    Abdulla, PA
    Jonsson, B
    [J]. INFORMATION AND COMPUTATION, 1996, 127 (02) : 91 - 101
  • [3] ABDULLA PA, 2006, P AVIS 2006 ETAPS 20
  • [4] Abdulla PA, 2007, LECT NOTES COMPUT SC, V4646, P99
  • [5] A Short Visit to the STS Hierarchy
    Bertrand, Nathalie
    Schnoebelen, Philippe
    [J]. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2006, 154 (03) : 59 - 69
  • [6] Unreliable channels are easier to verify than perfect channels
    Cece, G
    Finkel, A
    Iyer, SP
    [J]. INFORMATION AND COMPUTATION, 1996, 124 (01) : 20 - 31
  • [7] Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors
    Dickson, LE
    [J]. AMERICAN JOURNAL OF MATHEMATICS, 1913, 35 : 413 - 422
  • [8] Dufourd C, 1998, LECT NOTES COMPUT SC, V1443, P103, DOI 10.1007/BFb0055044
  • [9] On the ω-language expressive power of extended Petri nets
    Finkel, A.
    Geeraerts, G.
    Raskin, J. -F.
    Van Begin, L.
    [J]. THEORETICAL COMPUTER SCIENCE, 2006, 356 (03) : 374 - 386
  • [10] A well-structured framework for analysing petri net extensions
    Finkel, A
    McKenzie, P
    Picaronny, C
    [J]. INFORMATION AND COMPUTATION, 2004, 195 (1-2) : 1 - 29
12