+ All documents
Home > Documents > Synthesis of Nets with Step Firing Policies

Synthesis of Nets with Step Firing Policies

Date post: 14-Nov-2023
Category:
Upload: independent
View: 0 times
Download: 0 times
Share this document with a friend
25
COMPUTING SCIENCE Synthesis of Nets with Step Firing Policies P. Darondeau, M. Koutny, M. Pietkiewicz-Koutny and A. Yakovlev TECHNICAL REPORT SERIES No. CS-TR-1080 March, 2008
Transcript

COMPUTING SCIENCE Synthesis of Nets with Step Firing Policies P. Darondeau, M. Koutny, M. Pietkiewicz-Koutny and A. Yakovlev TECHNICAL REPORT SERIES No. CS-TR-1080 March, 2008

TECHNICAL REPORT SERIES No. CS-TR-1080 March, 2008 Synthesis of Nets with Step Firing Policies Philippe Darondeau, Maciej Koutny, Marta Pietkiewicz-Koutny and Alex Yakovlev Abstract The unconstrained step semantics of Petri nets is impractical for simulating and modelling applications. In the past, this inadequacy has been alleviated by introducing various flavours of maximally concurrent semantics, as well as priority orders. In this paper, we introduce a general way of controlling step semantics of Petri nets through step firing policies that restrict the concurrent behaviour of Petri nets and so improve their execution and modelling features. In a nutshell, a step firing policy disables at each marking a subset of enabled steps which could otherwise be executed. We discuss various examples of step firing policies and then investigate the synthesis problem for Petri nets controlled by such policies. Using generalised regions of step transition systems, we provide an axiomatic characterisation of those transition systems which can be realised as reachability graphs of Petri nets controlled by a given step firing policy. We also provide a decision and synthesis algorithm for PT-nets and step firing policies based on linear rewards of steps, where fixing the reward of elementary transitions is part of the synthesis problem. The simplicity of the algorithm supports our claim that the proposed approach is practical. © 2008 University of Newcastle upon Tyne. Printed and published by the University of Newcastle upon Tyne, Computing Science, Claremont Tower, Claremont Road, Newcastle upon Tyne, NE1 7RU, England.

Bibliographical details DARONDEAU, P., KOUTNY, M., PIETKIEWICZ-KOUTNY, M., YAKOVLEV A.. Synthesis of Nets with Step Firing Policies [By] P. Darondeau, M. Koutny, M. Pietkiewicz-Koutny, A. Yakovlev. Newcastle upon Tyne: University of Newcastle upon Tyne: Computing Science, 2008. (University of Newcastle upon Tyne, Computing Science, Technical Report Series, No. CS-TR-1080) Added entries UNIVERSITY OF NEWCASTLE UPON TYNE Computing Science. Technical Report Series. CS-TR-1080 Abstract The unconstrained step semantics of Petri nets is impractical for simulating and modelling applications. In the past, this inadequacy has been alleviated by introducing various flavours of maximally concurrent semantics, as well as priority orders. In this paper, we introduce a general way of controlling step semantics of Petri nets through step firing policies that restrict the concurrent behaviour of Petri nets and so improve their execution and modelling features. In a nutshell, a step firing policy disables at each marking a subset of enabled steps which could otherwise be executed. We discuss various examples of step firing policies and then investigate the synthesis problem for Petri nets controlled by such policies. Using generalised regions of step transition systems, we provide an axiomatic characterisation of those transition systems which can be realised as reachability graphs of Petri nets controlled by a given step firing policy. We also provide a decision and synthesis algorithm for PT-nets and step firing policies based on linear rewards of steps, where fixing the reward of elementary transitions is part of the synthesis problem. The simplicity of the algorithm supports our claim that the proposed approach is practical. About the author Philippe Darondeau is a Senior Researcher at INRIA-Rennes. He is interested mainly in concurrency, including Petri nets, and supervisory control, with applications to security. Maciej Koutny is a Professor in the School of Computing Science, Newcastle University. His research interests centre on the theory of distributed and concurrent systems, including both theoretical aspects of their semantics and application of formal techniques to the modelling and verification of such systems; in particular, model checking based on net unfoldings. He has also investigated non-interleaving semantics of priority systems, and the relationship between temporal logic and process algebras. Recently, he has been working on the development of a formal model combining Petri nets and process algebras as well as on Petri net based behavioural models of membrane systems. Marta Pietkiewicz-Koutny is a Lecturer in the School of Computing Science, Newcastle University. Her areas of research interest include: modelling and validation of concurrent systems, synthesis of Petri nets from transition systems and abstraction and refinement in process networks. Alex Yakovlev is a Professor in the School of Electrical, Electronic and Computer Engineering, Newcastle University. He developed the original Signal Transition Graph model, based on Petri nets, now used by academics and design engineers for modelling and synthesis of asynchronous controllers and interfaces. His research interests and publications are generally in the field of modelling and design of asynchronous, concurrent, real-time and dependable systems-on-chip, synchronisers and secure hardware design. Suggested keywords PETRI NETS, STEP FIRING POLICY, STEP TRANSITION SYSTEM, REGIONS, SYNTHESIS PROBLEM

��������� � ��� ���� ���� ����� ��������

�������� �������1 ������ ����2 ����� ����������������2 ������ �������3

1 ������ ���� �� ������������ ����� ������ ������

����������������

2 ������ �� �������� �������� �!����� "��#����$ �!����� ��� %$��� &' (�"� "����� )������� ������������ ������������������������

3 ������ �� &���������� &��������� ��� ������� &����������� �!����� "��#����$ �!����� ��� %$��� &' (�"� "����� )������

�������������������������

��������� %�� ����������� ��� ������� �� *���� ��� � �������������� �������� ��� ��������� �����������+ �� ��� ���� ��� �����,��$�� -��� ����#����� -$ ���������� #���� .�#�� �� ��������$ ���������� �������� � !��� � �������$ �����+ �� ��� ������ !� �������� �������� !�$ �� ����������� ��� ������� �� *���� ��� ������ ��� /����������� ���� ������� ��� ��������� -���#��� �� *���� ��� ��� � ������#� ����� �������� ��� ��������� ������+ �� � ������� � ��� /���������$ ���-�� �� ���� ���0��� � -�� �� ���-��� ��� !���� ���������!�� -� �������+ 1� ��� #���� ������� �� ��� /���� �������� ��� ���� ��#������� ��� $����� ���-��� ��� *���� ��� ����������-$ �� �������+ "��� ���������� ������ �� ��� ��������� $���� !����#��� �� ��������� ��������������� �� ���� ��������� $��� !������� -� ������� � ������-����$ ����� �� *���� ��� ���������� -$ � ��#����� /���� �����$+ 1� ��� ���#��� � ������� ��� $����� ������������ *%���� ��� ��� /���� ������� -��� �� ������ ��!��� �� ����!���� /���� ��� ��!��� �� ���������$ ��������� � ���� �� ��� $��������-���+ %�� ��������$ �� ��� ��������� ����� �� ����� ���� ���������� �������� � ���������+

���� �� *���� ���2 ��� /���� �����$2 ��� ��������� $���2 ������2$����� ���-���+

� �����������

������� ��������� � ����� ��� ������ ��� ��� �� ������ !��" ���� ���������� ���� ��� ���� !��" ���� ������" � ����� ������� �������� ��������� ������� � � ������� #�� �� !��� � � ��"�� ����$ %�� �� ������������������ "���� � � �� �� ��� �������� ���� ��� ���� ������������ "���� ����������� ���� � ��� ���� ������� �����#� ������� � &'()$

� *�+3������� ��+ ��

*��� �� ���� ��#����� ������� � #����� "��� � ��� ��#������ ��������# � #���� ����� ���� ��� ������"���� � ��� ���� � ����� ��� �� ����#���� � ��������$ +� �� #�� ��������� ��� ��� ���������!� ������ ��� ������ ��#����� �� ������" � ����� � ������� ������� � ��,���� ������ ��� �� ���� ������� ��� ��� #��� #�� �#�������� -�� ��� � ������������. ��������� ��#�����$ /����� ��� ��������� ���� ��#����� �� ����#��������� �� ����� ��# ��� ��� � ���� � ��� ��#����� �� #�����"����������$ +� �� �#��������� ������� �� ��,��� ��# � �������� ������ �������� ����� ������ �� � "��� #����"$ +� �� ����� ���� �� ��� � ��������������� #�� ������� ���������� ��������$

+ ��� ���� �����#�"� � ���� ��#����� ���� � ���� ��� ��������� ���������" ������ 0����� � ��� #���#���� ������� ��#����� �� ���� ��������� �����$ � ������� ���#��� � ��#�" ��� ������ � ������� ����� ���� ��� � ��� ���� +1� &'') ����� �� ��"�� � #���#�� ����� �� �� ��������� �� ��#�����$ ������ ��� #���#�� ���� !��" ���� ��� ���� � &'2)� #��� ��� �������� � ��#�� ��� ����� ��� ������ #���#�� ���� !��" ������� �������� � &'3) -�� ��� ��������" �������� �����# ������"����� &'4 '5). � #��� #�#���� �����#� �� � ���������� � ������� � ��������������� �#" ��� ������ ������� �#����� �� ��� ���� � �����#�����$����� ���� ����� � #��!�� ���� !��" ���� �� ������� �� ��� #�����" � ������� �������� �� ������������ � �������� ������� -�� ���� �� �������� ���������#�. ���##�" ��# �$"$ �����!� ��#���" ��#� �� ����$ + ���� ���������������� � ������� �����#� ��� �� ��#������ ���� ���� ���6 �� ���#���� ������� ��� ����������� � #��� �� ������ ������� �������� -� "����� ������������� ���� �� � ��"� � ������� ������� ��������.$

+ �� ���� ����� ��� ���� ���� ��#����� ��� � ������ #�����" ��������� ���� ��� #��� #�� ���������� �� �������� -��"����" ������ ��������. ���� ������ �������� ��� ��� ���� ������ �� ������ ��#�����$ *��� ��#�������� ��� #�� ��������� ��� ������� ����� ���� ��� ������ ��� �#�������� ������" -�� ���#��� �� �� ���������� �����"�������� � � ��� � ������ ��"�������� � ���� �� ���� ��#����� ����� ��" ��� ��#� �� � ������� ���� ��#������� #��� #�� ��7����.$

+ � ��� ���� ��#����� �� � �#��#��� ������ ������������ � �� ��������#����� �� ������������� � ������� ���� ��#�����$ 8��������� �� ��������� ##�� ��� �#��#��� ��� �� ����� �������� ��� � ��� �#�������������� � ������� ����� �� ��� ���� � ������ �� � !� ���" � ���������$��� ���� ����� � ���� � ��� �� � ������� ���� �����# �� �������" � "������������ � ����� ���� �� ����� � #����� ��� �#�������� ������ �������$ %��� ������� ���� �� ������ ���� ���� �������� -����� �� ���� � ��#����������� ���� �������.$ + ���� �� ��� � �������� ��� ��� � �������� � ��������� � � "��� #����" � � ����� �� -�$�$ ����� �#������� ���� ��� ������ ������ � ���� #����". ���" ���� �������� � ������ �#� ����� �� � ��������� ��� ��� �����$ ������ �� ��� � ��!� � � " � "����� ����#������# ���� ������� � ��� ������� �� �������$ %������� � ��� !��� ����� ��� ����� �� ������ � "����� ����� � τ ���� ����� ��� ����#���� τ �� �

�$����� �� �� !��� ���� ������ *������ �

-����. ������� �����# ���� ������ �� �������� ���� ���� ��� ������� �����#����"� ��� ������� ����������� ������ ������ �� �������� �� ������������� -��� ���� ��� ���� � ��#���� ����#����� ��!��� ���� ������� &'9).$ %�� !��" ���� � τ ���� �������� �������� � ������� � ����� �� �������#����� �� ��� ��������� � :����; ���� ��#�����$ *��� !��" ������� ������ ��!�� �� � τ ���� �������" � � ���� ��#����� #�� ����������� ������ ���� ���� ��#�����$ � ������� ������� � ��� ������� �� ������ �� ����� ���� �� �� �������� �� �� ������ ����� ������ �� ��� ��#� #����"$%��� ��0���� ��� ���� ���� ��� ������ #��� ����� � ����� ��� ������ � ��� ������� �������$ � ������������ ��#��� ���#��� � ������� ��� ���������� �� ��������� �������� � �����$ <��� ���� !��" ����� ������ ����� �������" �� ���� #����" ��� ����� ���� ��� � #���#�� �$�$�$ � �#"��� ������� ������ �����$ *��� ������� ���� �������� ��# �� ���� ��������� #���#�� !��" ���� ��# &'3)$ /����� �� ����� ��� ������ ������������������ ���� !��" ������� ����� ��� �� �������� �� ��������$ +� ����� ������ ���� ������� �#��� � "����� � ���������� ���� -������������ ������ ����"�����" ������� ������� � ������� ���������. ����� "�� �"������� ����� ����� �� ��������$ %������� ���� ������� ����� �� ��!�� ������ �� ��� �������� �$"$ � ��� ����� � ��#����� �� ���� � ����� #�����" � �������� � �����#���� �����#�$ =��� ���� ����� ���� !��"������� #�� ����"� ����� ��� �� ������ !���� � ��������� � �"�����"$

��� ����� ����� � ���� � ��� �� � ��� ���� ��� ���� ���� !��" ���������� �#����� � �������� �����$ =� � ���� �� ������" ��� �������� � τ �������� ���� !��" �������$ + ���� � �� ���� � ����� �� �������� ��� �� ��������� �����$ %�� ����� ����� �� �������� ������� ������ � !��" ������� �"��� ������� �����# #�� �� �������� �� � ����� �� ���� ���������� ���������������$ ������" � ������� � ��� �� � ��������� ��!�� �� �������� #�� ������ � ���� �����# ���� ��� ����� ���� ����� ��#��� ����� <��������� �� >�����" &2 '?)$ +� � ������� �� ������ ��������� ���� � ������� �����# �� �������� �� � �� �� �� �� ��#����� � ��� �� ������������������ "���� -� ���� "����. � ���� ��$ <��������� �� >�����" �������"���� ��� ��������� � ������� �����#� �� ���#����� ��� �� �������� ���#���� �������������� � ��� ���������� ������� �����#� � ���#� ���"�� &2 '?)$ � ����� �� � ��� � ������ ����� �� ����#�� ������ � ������ ����� �������� ���� � �������� �����$ %� ���#� ������������ ��� �� ����������������� �����#�$ %�� *���� *������� ���# �� ����� ���� �� ������� ��������� �����"������ �� �� ����� � ��"�$ %�� @����� ������ ���# �� ��������� �� ���� ���� -�$�$ ������� �����. � ����� �� ����� ��� �������� ������� �������� �� ��������� �� � �## ��"� ��# ��� ������ ����� �������� �����$ %�� ��������� � ������� �����#� �� ���� ����� �%���� ��� "����� �%���� ��� ������������� �� ��#���� ���#� � &' 3) ���" ���������"�� ������� �� &5 '()$ ������ &') ����� ���� ��� ��������� �����# ��!��� ������� �����#� �� �%���� �� �� ����� � ��#� ���#��� � ������� � ��� ������� �����#$ >�"��� ���#� ���� ��� ������ � ������������������� �����#� ��#����� � �� ������ ���� "����� � ���#����� ��� ����

� *�+3������� ��+ ��

������� ���� � &9)$ +� � ������� ������� ��������� � ��� � ���� �������� �����# #�� �� �������� �� � �� �� �� �� ��#����� � ��� ���� ������������"���� � ���� ��$ � ���#���� �������������� � ��� �%��� ���������� ����������� �����#� ��� "��� � &'() ����� � ������ � ��� ���� � ��"��$+� ��� ��� � &3) ���� ���� �������� �����# �� �� ����� � ��#� ���#���� ��� ���� � ��� ���� ������� �����#$ � ��#���� �������������� � ���� �������� �����#� �������� �� ���#����� ��� ���� ������� ���� ��� "��� � &'A)$ ������������������ �������� ���� #�� �� ��������� �� ������� � � "����� ����������������� � &3) �� &4)$ 1�#��� �� ���� ����� � ��� ���� ��������� �����"�� � � ������� �����# T #�� �� �����!�� ���� ��� #�����#� ��# T �� -����. ������� �����# τ ������� � ���� �����$ � ���#���� ��������������� τ ��� ���������� ������� �����#� � ���#� � τ ���"�� #�� �� ������������� �� �� ��� ���" τ �� � ����#����$

%�� ����� ������� &'4 '5) ������"���� ��� ��������� � ���� ������� ������#� �� ���#����� ��� ���� ����� ���� �� ���� ��� ������ #���#�� !��"���� � &'3)$ %�� �� ���������� ���� ������� �����#� ��� ������������� �� ���*���� *������� ���# � ������� ��# � ��� @����� ������ ���# �� ��� ����#����� ���#$ =� ���� ����� ���� �������������� � ��������� τ ���� ���� ���� !��" ������� ������ �� ��������� �������� � ����� ���" �������� � ��"�� ��!�� �� #�����#�$ @� #�� "����� ���� !��" ������� �� ���� ��� ��� ���� ��� �� ���������� ���� ������� �����#� #�� �� �������������� ����#�� �� �� ���#� ��� ����� *���� *������� ���# �� � #��������� @����� ������ ���# ����#����� τ �� ��� ���� !��" �����$ ������ ������� �� ������� ��� ��� ������� � ��� ���� ������ ���������������$ %��� ����� �� ������ �� ��� ��!��� � � ��"����# �� ��� ���������� ���� ������� �����#� �� �%���� ���� ��� ����� � #���#���" ����� �������� � ����� ����� !��" ��� ������ � ���#����� �������� �� ���� � ����������� �����#$ %�� ��#������� � ��� ��"����# ������� �� ����# ���� ��������� ������� �� ���������$

��� ������

+ ���� ����� �� ������ �#� ����� ��!���� �� ����� �����" ����� ��� ������" � "����� �� � � ���� � ��� ��!�� �� � ������� �����# ������������ ��� ������� ����������� ������ ������ �� ��������$

������� ����� �� ��������� ���� � ���� ����� �� � ��� S���� � �##������� �� ���������� ����� -�#�����. ������ + S ��� ������ ���#�� 0$ %�� #�� ���#�� �������" ��# �#���" n ����� �s ���� �� ����� �� sn � n · s$ + ���������� 0 = 0 · s = s0$ =� ���� ����� ��#� �����!� ������ #���B -�. ��� ��� � ������ �#���� N -������" ���.���� ��� �����#���� ������ �� 0 = 06 -��. SPT = N × N ���� ��� ������������� ������ �� 0 = (0, 0)6 �� -���. SENC = N×N×{0, 1}× {0, 1} ����0 = (0, 0, 0, 0) �� ��� �#����� ������B

(w, x, y, z) + (w′, x′, y′, z′) = (w + w′, x + x′, min{1, y + y′}, min{1, z + z′}) .

�$����� �� �� !��� ���� ������ *������ �

� �� ����� ������ (Q, S, δ) ��� � ������ #�� S ������ � � ��� ��� ��� Q �� � ������� �� ����� ����� δ : Q×S → Q ���� ���� δ(q,0) = q ������� ����� q ∈ Q$ � ���� ����� ������� �����# T = (Q, S, δ, q0) �� � ������������# ���� � ���� � ����� q0 ∈ Q �� ���� ���� ���� ����� q �� �� �� ��� �$�$ ����� ��� s1, . . . , sn �� q1, . . . , qn = q ���� ���� n ≥ 0 �� δ(qi−1, si) = qi ��1 ≤ i ≤ n$ @� ����� ����� q � � -����������� � ����������. ������� �����#TS �� ���� ���� �� enbldTS (q) ��� ��� � ��� #�� ���#��� s ����� ���� ���� �� q �$�$ δ(q, s) �� ��!��$ � ������� �����# �� ���� �� �� ��� !�����#�� ������ �� ��� ��� � ������ ���#��� �� �� � ��� ������ �� !���$ +��� ���"��#� � ������ ����� ���� �� ���������� �� � �#��� � ���� �� ��� �����#���" ��� �� �������$ %�� ������� 0��������� �������� ���� �� #�����$

+ ���� ����� ������� �����#� ���� �� ���� �� �� ������ ��,���� ��������$ @���� ���������� ������� �����#� T ��� ������ ���� ������ #������� �������� ������� ��������� � ����� ���$ =� ���� ���� ���# ���� �� ������ ������� � �������� �� �� ������ �� ���$ *��� ����������� ������������#� τ ��� ��������� ������ #��� ���� ������ ���� � ��!� ������������� � ���$ =� ���� ���� ���# �� �����$

%���"��� ��� ����� �� ���� ����#� ����B� T �� � !��� !��� ��� �� 〈T 〉 �� ��� ���� ������ #�� "�������

�� T ���� α, β, . . . ��"�" ��� ��� ���#���$� T = (Q, S, δ, q0) �� � !��� ���������� ������� �����# ��� S = 〈T 〉$� τ = (Q, S, ∆) �� � !��� ����������� ������� �����# ��� �

������ #�� S$

%�� ��� T ���� �������� � ��� � ����� �� ��������� �� � 〈T 〉 C ��� �� ������ � ��� ��� #��������� ��� T C �#������ ��� ������� ����� � ��� ����� ������ T $ �� ������� �����#� ��� 〈T 〉 ���� �� ������ ���� �� ����� �������$

@� ��� t ∈ T �� α ∈ 〈T 〉 �� ���� ��� α(t) � ���� ��� #����������� � t� α �� � α =

∑t∈T α(t) · t$ 1�� ���� 〈T 〉 �� ��#����� � ��� ��� � ���

#����"� ��# T � N ���� ������� ������ �� ��� ����� #�� 0 �� ������� ���#��$

������ �� ��� ���� � ����� �� � ���������� "���� N = (P, T, W ) ����� P �� T ��� ������ ���� � �������� ������������ ������ �� ��� �� �� ������� �� W : (P ×T )∪(T ×P ) → N �� � ��� � �������� ��"�� ���� ��"��������"�� ���"���$ � � ���� � N �� � #����" M : P → N �� � ����� ������� N = (P, T, W, M0) �� � �%��� ���� � ���� � #����" M0$ =� ���� ��� ���������� ������ �����" ��� "�������� ����������� � �%��� �����#�$

D��� � �%��� �����#N = (P, T, W, M0) � ���� α ∈ 〈T 〉 �� � ���� �� #���� ���� �� � #����" M �� �� ����� ����� p ∈ P M(p) ≥

∑t∈T α(t) · W (p, t)$

@���" ���� � ���� ����� � ��� #����" M ′ �� ����� p ∈ P ��!�� ��B

M ′(p) = M(p) +∑t∈T

α(t) · (W (t, p) − W (p, t)) .

� %�������� �� ��� ��4�� ������$ ���� ��������� �� ��������� $���+� �� ����� ��� �������� a3b = {a, a, a, b}+

5 *�+3������� ��+ ��

=� ���� ���� �� M [α〉M ′$ %�� �������� �� �� ������ �� �� CRG(N ) � N�� ��� ���� ������� �����# CRG(N ) = ([M0〉, 〈T 〉, δ, M0) �����

[M0〉 = {Mn | ∃α1, . . . , αn ∃M1, . . . Mn−1 ∀1 ≤ i ≤ n : Mi−1[αi〉Mi}

�� ��� ��� � ��������� #����"� �� δ(M, α) = M ′ �� M [α〉M ′$=������ M [α〉M ′ �� α #�� �� ���#���� �� �#����� ����� β �� γ -�$�$

α(t) = β(t) + γ(t) �� ��� t ∈ T . ������" � ��� ��!��� � ���� ��#����� ����� #��� ����� � �������� �� #����" M ′′ ���� ���� M [β〉M ′′ �� M ′′[γ〉M ′$%��� �����!� ������� �� � ��0����� � �� ��!��� � ���� ������� �����#������ ������ �����;� ��"��� ��!��� &'()$ + ���� ��� ��� ������ � �#����� !��" ������� �� � �� ������ ����#������ #����"�$

���� �� ��� ���� � ��������� ���� τ = (Q, S, ∆) #�� �� ������ � ����#���� � ��� ��!��� � � ����� � ���$ <��� ������� τ �����!����� ������ -#����"�. ���� �� �� ����� ����� �� ������ -Q. ��� �������-��������� 0� ����. ���� � �� ������� #�� �����# ����� ������ -S. �� ��� �����" ����� �� ����� � �������� -∆.$

��������� � �τ������ � τ ��� �� ���� ����� �� �� (P, T, F )� ����� P � T �� ������������ ������� ���� � �� ��� � �� ������� � F : (P × T ) → S� �#����" � ��� τ��� �� � � M : P → Q� � τ ��� �����# N �� τ��� ���� ���� � � ���� M0�

%���� �� � ����� ��#������� ������ ���� ��!��� �� ��� ��!��� � � �%��� �����#$ %�� �� �������� ��,����� �� ���� � τ ���� � ��"�� F (p, t) �� ������ � ���� �� �� ��� ������� ���� ������ � ����� p �� ������� t$ +���������� �� � � �%��� �����# W (p, t) = m �� W (t, p) = n ��� ���� �� ����������� �� �����" F (p, t) = (m, n) ∈ SPT $

��������� � ���� ��������� ���� τ��� ������ N = (P, T, F, M0)� ���� α ∈ 〈T 〉 �� -�������. ������ � � ���� M � N �� �� ����� p ∈ P �∑

t∈T α(t) · F (p, t) ∈ enbldτ (M(p))� � ����� ���� �� α ∈ enbldN (M)� ���!��" � ���� ���� �������� ��� � ���� M ′ ���� �� �� �� ����� p ∈ P !

M ′(p) = ∆(M(p),

∑t∈T

α(t) · F (p, t))

� ����� ���� �� M [α〉M ′� � ��� ���� ��� ������� ������������ "����CRG(N ) � N � ��� ���� �� ����� ������ ����� �� ���� ���������� ���M0 �� �������� "��������# � ���� ����� � N �

�� � &4) �%���� #�� �� ��������� �� τPT ���� ����� τPT = (N, SPT , ∆PT )�� � �!��� ������� �����# ��� ��� ������ #�� SPT ���� ���� ∆PT (n, (i, o))�� ��!�� �� n ≥ i �� �� ��� � ��� � n − i + o -��� @�"��� '-�..$ +��������� F (p, t) = (i, o) #��� ���� i �� ��� ���"�� � ��� ��� ��# p � t �� o ���

�$����� �� �� !��� ���� ������ *������ (

(a)

4 10

(3, 9)

��������� ���������

(b)

0 1

���������

���������

���������

���������

���� �� 6�� �� ��� ��������� �� τPT (a)2 ��� ��� /���� ��� �$�� τENC (b)+

���"�� � ��� ��� � ��� ������ �������$ % ������# � �%��� �� � τPT ��� ���� ��� ��#� ������� ������������ "���� ��� �� ��� � � �� � ���F (p, t) = (W (p, t), W (t, p)) �� ��� ������ p �� �������� t$

<��#����� ��� ���� ����� ���� ���� ��� ������� ���� ��#����� ��!��� &'5) #�� �� ��������� �� τENC ���� ����� τENC �� � !��� ������� �����#��� ��� ������ #�� SENC ��� � @�"��� '-�.$ +��������� �� F (p, t) =(i, o, inh, act) ��� ��� #���" � i �� o ��� ��� ��#� �� � ��� ���� � �%�������� ����� inh = 1 �������� ���� ����� �� � ������� ��� ������ p �� t �� act = 1 �������� ���� ����� �� � �������� -� ����. ��� ������ p �� t$

� �������� τ ����� %�� �������� �����# �� ��� � � � ������ �����#�� � �������� ���������� �����#$ E ��� � ��� � ���� �� � ������� �������� �,������ -�$�$ ���������. �������������� � ��� ������� �����#����� �� �� �������� �� ����� ���$ E ��� ���� ��� � ����� � ������������������ �� ������" ����� ��� ��# ������� �����#�$ %�������� � ��"����#��������" ���� � �� �� � ��������� � � �,������ ����� � ��� ����������������#$ + ��� ���� � τ ���� ��� �������� �����# �#���� ��� �����" �����������#�$

�����������

������ �������� �� ��7���� ������ �� � "��� T � �� �� ����� ���#� τ ��� �����# N -�$�$ T ∼= CRG(N ) ����� ∼= �� ������� �����#��#�����# ��������" ��� ������ ������ �� ������� ������.$

������� ���� �����

D��� � !��� T ������� � !��� τ ��� �����# N ���� T ∼= CRG(N )$

1�� ���� ��� ������ ������� T �� �� �������� �� �#� τ ��� �����# N ��� �#������ ���������# � ��� ������� ���� ����� �����#$ >������������� ������� �����#� ���� ��� ������������� � &3 4) �� �� ���#� ����#����� τ $ %�� ���#� �� ���� ��� ������� � � ��7������ ���� ��#��� � τ ������� ��!�� �� #�����#� ��# T � τ $

��������� �τ��������� � τ ���"� � T �� � �� (σ, η)� ����� σ : Q → Q

� η : 〈T 〉 → S �� �������� � ������� ���� �� � �� �� q ∈ Q � α ∈ 〈T 〉!

η(enbldT (q)) ⊆ enbldτ (σ(q)) � ∆(σ(q), η(α)) = σ(δ(q, α)) .

7 *�+3������� ��+ ��

$�� ����� �� �� q � Q� �� ����� �� enbldT ,τ (q) ��� ��� � �� ����� α ���� �� �η(α) ∈ enbldτ (σ(q))� �� �� τ������� (σ, η) � T �

1�� ���� ��# ��� ��!��� � � τ ���"� �� �##�������� ����� ���� �� ���������� q � T B

enbldT (q) ⊆ enbldT ,τ (q) . -'.

+ ��� ����� � ��� �������� �����# � τ ���"� ��������� � ����� p �������� ����� -� τ. �� ������� ���� ��� "���� ����� -� T .$

+� ���� �� ���� T �� �� �������� �� � τ ��� �����# �� ��� �����" ����"��� ���#� ���B

����� ���� �����

@� �� ���� � ������� ������ q �� r � T ����� �� � τ ���"� (σ, η)� T ���� ���� σ(q) = σ(r)$

�� �� � ���� �

@� ����� ����� q � T enbldT ,τ (q) ⊆ enbldT (q)$+ ���� ���� �� ����� ����� q � T �� ����� ���� α � 〈T 〉\enbldT (q) ����� �� � τ ���"� (σ, η) � T ���� ���� η(α) /∈ enbldτ (σ(q))$

+ ���� ��� ����� ���� ����� �� �� �� � ���� � ������ � ������ ��� ����������� �����#$ %�� ��� ����� �� � ������ ��� ������� ���

�� ����� �����# �� � !��� T $ %��� �� �� �������� ���� � "����� ������"� T #�� �� �������� �� � τ ��� �����#N �� #�� �� �#������� � ����������� !��� N �� ��� �� ��� �����" ���#���$

%& ���� '� F�� T = {a} �� T �� � ��"����� ������� �����# ���� �0��� �� ��� ������ �����$ ������ ��� τ = (N \ {0}, {xn | n ≥ 0}, ∆) ��� �� ���� ���� ���� ∆(m, xn) �� ��!�� �� n = m$ %�� ����� �� � τ ������� � ������� ������������ "���� ��#����� � T $ ��� �� ��� � ���� ��BP = N \ {0} T = {a} �� �� ��� n ≥ 1 F (n, a) = x �� M0(n) = n$ /����� !��� τ ��� �� "������ T �� � ����� �� ������� �� #�� � ���� an$ ��

� ����� � ��� ������� ���� ����� �����# �� ������ �� � ���#���� � !��� ��� WR � τ ���"�� � T �������� ��� ���������� � ���������� � ��� ��"��� ���#� &G)$ � �������� τ ��� �����# �� ��� NWR =(P, T, F, M0) ����� P = WR �� �� �� ����� p = (σ, η) � P F (p, t) = η(t)�� M0(p) = σ(q0) -������ ���� q0 �� ��� ������ ����� � T �� T ⊆ 〈T 〉.$

+ ��� ���� � �%���� τPT ���"�� ������ ���� ��� ��"�� ��!�� � &'()����� � ��#���� �������������� � �%��� ���������� ���� ������� �����#� �������������$ %�� ������� ���� ����� �����# #�� �� ����� &3) ���"��#� ���#��� � |Q| |T | ��� #���#�� ���� � � ���� α ���� ���� δ(q, α) ����!�� �� � ��������� q �� ��� #���#�� �#��� � #��#�� ����� α �������� δ(q, α) �� ���!�� �� !��� q$

+ ��� ���� � ���#����� ��� ���� ����� ���� τENC ���"�� ������ ������� ��"�� ��!�� � &'5) �� ��� ������� ���� ����� �����# �� ������� ������� ��� �#��� � τENC ���"�� � � !��� T �� ��� !��� -��� ���������# �� 1���#�����.$

�$����� �� �� !��� ���� ������ *������ 8

1�� ���� �� ���#���� ����� � ��� ����������� �����# ����� �������� � ������ enbldT (q) = enbldT ,τ (q)$ + ���� � ��� ��������� ����" ������� -'. �� �� � ���� � �� ���� ��7���� �� ���� ������$ /����� ���� ����� � !��" ������� ���� :�������; ������ ���� �� ��� �� �� ����� � ���# ���� �� � ���#� � � ������ ������ ��� ������ ������ ����� �����$

� ���� ���� ������

=� ������� ��#���� ���� !��" ������� ����� ������� #������" ���#����$��� ���#���� ��� ��#��� ���� !��" ������� ������ �� � �������� � ��� ����� � 〈T 〉 ���� ��� ���#� ���� � ������� ������ ���� α �� -����.�������� ������� ����� �� ����� ������� ������ ���� β ���� ���� α ≺ β -�$�$ α � β �� β � α.$ /����� ��� !��� ���#��� ���� ��#��� #��$

%& ���� (� + ��� ����� � � �������� �����# ����" ������ ���� a �� b��� �������� ����" �� ����� ������ �� � ������� ����� #������ #������������ � �## ���������� ������� �� m �� � ������� ���������"�#� �����" ���� ���� ������� �$"$ ��� ������ ����� ��#���"$ %�� ������� ��������" m �� ���� ���� ��� �����" �������� �� �� ����� �� ��� ��������"�� �� � � �������!�� ����� �����$ %��� �� �� ��� �������� ���� ��� ��������� �� �� � ��� ��)��� ��������� ����� ����� ���� �� ����� ��� ������ -�����"��� � �� �� ������.$ + ���� � �0��� ����� ��� ������� #�� ��������� �#��������� � ��������� ����� �� �������� �� ��� �� ������ ��������$

%�� ���� ����� ����� � ��� ����� ���� � � �� #��� � ��� �����# ������� m ����� � �� ������ � !�� � �� #����" ����� ��� �� �����"�������� a �� b ��� ��� ������$ E�������� m ����� �� ������$ %����������� �� �� �#���#���� ���" � ���� -� '������. �%��� �����# ��"����� ���� � ����� ���� ������� m ��# ���" !��� ������� ��� a �� b��� ��� ������$ =����� ���� � ����� ���� �%��� �����# �� ������� ������������ ���"� ����� �� � 3������ �� ��������� �� ���� �� � ���� �� ���������� ���� ����� �������" ��������� �� ��� ������� �� &A)$ ��

%�� ���� ���#��� ��� ���� ���� !��" ������� �� �#���#�� �� ������ ��������" � #�� "����� ����� � ��� �$�$ �� ���"�" ��� ������, ������������� ��������� �� ���� ���������$ /����� �� ��� ��� ���#������� �����" ����� #����"� #�� � �� ��"� �� ���� ������$

%& ���� *� ������ ��� ���� ������� �����# � @�"��� 3-�.$ +� �� ���� � ������� �� ��� �� �������� �� �� �%��� � �� �� ������� ����� �� ������������ ��� ����� ������� ����� �����" ���� �� ���#��� �� ��� � ������� ���� a � ��� ������ �����$ /����� �� �� ������� ��� �%��� � @�"��� 3-�.���� ��� #���#�� �������� ���� ��� ���� �� "�� �� ������� ��� ���"������ ������� �����#$ -1�� ���� #���#�� �������� �� �� �������� �� ���������� 〈T 〉 ��������" � #������� ������$. ��

'� *�+3������� ��+ ��

(a)

aabbb

(b)

2

3

6

a

b

��

���� �� %�������� $��� !���� ������ -� ������� !����� � ��� /���� �����$ (a) ������ �����$��� *%���� ��� �� ���������� (b)+

%& ���� +� <��#����� ��� � &'4) �� ���#����� ��� ���� ����� ���� � &'5)���� ��� �������� ���� � �������� ��#����� #�� ����������� ��� ��!���� 3$ + ��� ������ ��� ��� � �������� T �� ��������� �� � ��� ��� � ��������� ≡ �� ��� �� �� �������� �� !��" ��� #���#�� ������ ����� �$�$�$ ��������" ������� -����� ���� ��� ��#��� ���� � #��� T → {0, 1}.B α � β ���� ��� t ∈ T α(t) = 1 ⇒ β(t) = 1 �� β(t) = 1 ⇒ (∃t′) (t ≡ t′ ∧ α(t′) = 1)$ ��

%& ���� ,� % ������� ��� �������� � �%���� ���� ������ ��������� �� ������������" ��#����� �� ��7��� � ����� ���� t � t′ �� ��� ������� � t �� ������� � � ��� � ��� ������� � t′ �� ���� t + α ≺ t �� ��� α = 0$ ��

%& ���� -� % #���#��� � �������� ����� � �� ���� � ��� �� #��$ : T → Z �� ����#� ����B α �$ β ��

∑t∈T α(t) · $(t) ≤

∑t∈T β(t) · $(t)$

@�"��� 4 ���� � ��������" ��� ���� � ������" ��� ������ ����� ����!��" ����� ���� $(a) = 1 �� $(b) = −1 � ��� �%��� � @�"��� 4-�.$ %���������" ������� ������������ "���� ��� � @�"��� 4-�. ��� �������� ��� ������ �������� ��� � ��� ������ ������� ����� ���� ��� �������� a ��b ��� �������$ =� ��� ��� ��� ������� ����� �������� � @�"��� 4-�. ����������� ��� ��"��� � ����� ������" ������� �� ���# �� ��� ��"��� ���������$ ��

%& ���� .� ������ � �%��� ������" � � ������� a �� ������ �������� ���� � ����� ������ �� ��� ������� ���� ���� am � an �� m ≤ n$+ ���� � �� ��� ����� ��� 〈T 〉 ��� ������� ������ ��� ���� ��� ��� ���������� ��� !��" ���� �����$ ��

% ������ ��� ���� �������� �� ���� ���� ���� !��" ������� ��� � ��� ��������" ������� ������� � ������� -� ��������. �����#�$ ������� �� � ���� � ������� � ������� ������� �����# ��� ��"�� ����������� � ���� !��� � ������ #�����" �� �������� ������� �� ��� � ��� � �������� ������ �� �� � ���� ����� �� ��� !� ���" � ��� ��������$

�$����� �� �� !��� ���� ������ *������ ''

(a)

a

b (b)

ab

ab

(c)a

b b

a

aa

bb

���� �� %�� �4��� �� ����$��� � ��!��� -��� /���� ������� �����$+

=� ���� � ������� ��!� ���� !��" ������� �� ����� �,��� �� ���������$ %���"��� ��� ���� � ��� ����� Xτ �� � ��#��� �#�����" ��� ����enbldN (M) ���� ���� N �� � τ ��� �����# �� M �� � ��������� #����" � N $+ ���� ���� Xτ ����� �� ��� � ������ ����� � �� ��������� #����" ��� τ ��� ���� ��� � �������� T $ + � ���� ���� �� ��� �� ��� � ���� ������ ��!�" �� �����" ���� ������� τ ��� �����#�$

��������� ! ���� ����� ����� �� � ���� !��" ����� ���� 〈T 〉 �� ���� �� ������ ��� ���� ����� � ���� cds : 2〈T 〉 → 2〈T 〉 ���� �� �� �� �� X ⊆ 〈T 〉 �Y ⊆ X!

'� cds(X) ⊆ X/(� cds(Y ) ⊆ cds(X)/ �*� X ∈ Xτ � X \ cds(X) ⊆ Y ����� cds(X) ∩ Y ⊆ cds(Y )�

+ ��� ���� X ����� �� ������� �� ��� ��� � ������� ������ ����� ���#� ��������� #����" � �#� τ ��� �����# �� X \ cds(X) �� ��� ������� ������ � ���� ����� �� ���� #����"$ %�� ����� cds(X) ⊆ X ��� ���������� �� �� �������� ����� �� ���� �� ������$ % ��� ��� ������������ ��� ���� ������ �#�"�� ���� ���� �������" � ���� α ∈ Y ����� � ��� -�������. �����" � �#� ��� � ����� DisSetα

1 � DisSetα2 � $ $ $ $

%�� ��!��� 5-3. ��#��� ������ ���� ���� ��� DisSetαi ���� �� ������ � Y ��

��� ������ � X �� � �������� α � X �� ����$ ��!��� 5-4. �� #�� �������� ����� ��� ������ ���� �� ����� � �������" ��� DisSetα

k �������� �$�$ DisSetα

k ⊆ X \cds(X) �� �� ������ � Y $ * �� α ∈ Y �� ��� ���� ��������� X ��� �� ���� ��� �� ���� �������� � Y $ /��� ��� ���� �� ������������� ��,���� ����� � #������$

��������� " ����� ��� ��� ����� ����� �� 0�� N �� � ������� �cds �� ���� ���� ������ �� N � ������� cds �� N ������� � ���� �������" � � �� � ���� M �� ��� �������� � ���� ����� �� � ����� �� cds(enbldN (M))� � ���� ��� CRGcds(N ) �� ����� ��� ������ �� �� ��� ���������� � CRG(N )�"1��� �� � CRGcds(N ) � � �� ���� ��� ������ CRG(N ) �� ������# 2���������

enbldN ,cds(M) = enbldN (M) \ cds(enbldN (M))

���� ����� ��� ��� � ����� � ���� � �� �� ��� � ���� M ���� ������ cds�

'� *�+3������� ��+ ��

E� ������ ������� � ��� ��������� �� ����� �� ���� ����" � ����� � � ������� �� �� ������ ��� �������� �� � ���������� �� ���� ��� � ������������ �� � ������ �$ +� �� �#����� � ������ ���� ��� �������" ����!��" ������� ���� �� #�� ��� ���� B ���� �� ��� � �� �� ��� ������$@� ���#��� ����" � ����� ���� �������� � ������� ���� ��"� ������� #�������� � ���� �����" � ������� ���� ���� �������$

<��#��� A ���� � ������� ����� ����� �� � �!��� ���� � ����� ���� ����� �������� �� ��� ��������$ %��� ������ ������� ����� ������ �#���#������ �����#� �� ����� �� �� ����� -4. � ��!��� 5-4.$ + ���� ���� �������� � 〈T 〉 ������ � ���� !��" ����� ���� �� �������� �� ������� �� τ ��� N ��� �������� ������� ����� �� ��� ��� ������� �$�$�$ N �����#��� ���� �!��� ���� � ����� α1 ≺ . . . ≺ αi ≺ . . . �� ���� -�������.������ �� �� #����" � CRG(N )$

%�� ���� !��" ����� ������ �� � ������� ������ � 〈T 〉 �� "��� ��B

cds�(X) = {α ∈ X | (∃β ∈ X) α ≺ β} .

*��� � ����� ������ � ���� �������" ��� ���� ������� ������ ����� �������� � �� ��#���#��$

���������� �� 3 �������� � � 〈T 〉 �� ��� ��� ������� ������ ����� τ���������� ��� cds� �� ���� ���� �������

����� ��!��� 5-'. �� ������� �����!��$ % ��� ��!��� 5-3. �� ���� Y ⊆ X�� α ∈ cds�(Y )$ %�� �� ��� ��!��� � cds� ����� �� β ∈ Y ⊆ X ���� ����α ≺ β$ /��� �� ��� ��!��� � cds� α ∈ cds�(X)$

% ��� ��!��� 5-4. ����#� ���� X ∈ Xτ Y ⊆ X X \ cds�(X) ⊆ Y�� α ∈ cds�(X) ∩ Y $ =� ��� � ��� ���� α ∈ cds�(Y )$@�# α ∈ cds�(X) ∩ Y �� ����� ���� ����� �� β ∈ X ���� ���� α ≺ β$ =� ������� �� �����$���� 'B β ∈ Y $ %�� �� ��� ��!��� � cds� α ∈ cds�(Y )$���� 3B β ∈ X \ Y $ %�� �� X \ cds�(X) ⊆ Y �� ���� ���� β ∈ cds�(X)$/��� ����� �� γ ∈ X ���� ���� β ≺ γ$ +� γ ∈ Y �� ���� ���� ' ���� β = γ�� ���� α ∈ cds�(Y ) ��� � ��� ����������� � ≺$ E�������� �� ���� ���� 3���� β = γ �� � γ ∈ cds�(X)$ �� ��� �� ������ ��� ��#� ��"�#��$ 1� ������� � �� ������ ������� �$�$�$ ��� τ ��� �����#� �� X ∈ Xτ � #���!� ��� � ����� � ���� ������� �#� φ ∈ Y ���� ���� ���� ' ���� ����β = φ �� � α ∈ cds�(Y )$ ��

1� ��� ����������� ������� ���� !��" ������� �� �� ��!�� �� ��������$@� ������ ��� � ��������� � <��#��� 3 ��� �� ����� ���� �� �� cds�-�� ���� ��� �������� a, b, m ���� ���� ��� � ��� ��#� ���� �� ��� ���������� �� ������.$ /����� ���� ���#��� �� ������ ������� ���� ��� �����cds ���� ���� µ ∈ cds(X) �� µ(m) ≥ 1 �� ����� ��� α, β ∈ X ���� ����α(a), β(b) ≥ 1$

=� ���� ���� � ��� ���� ��!��� 5 ��#� ����� ��� ������� �� #�� ��������� ��!��� � ���� !��" ������� ����� ��������$ 1�� �������� ���

�$����� �� �� !��� ���� ������ *������ '�

������� !��� �� ����� ������� ����� �������$ ��!��� 5 ��� ��� ����� �����" � ��#����� ��� �������� ������#�� � ���� ������� ����#��$ ��!��� 5���������� ��� ������� ��!��� ��� � ������� ������� ����� -4. �� �������� �� � "��� � #�� �#���� �������������� � ��� �� ���������� �������� �����#� -������ ��� � &�� ���� ���#.$

� �������������� �� ��� ��������� �������� ����� �

=� � ���� ��� ���� #�� ���������� ������ ���� � ���� ����� ������� ���� �������� ��� �� �������� �����# ��� ���� ��#� ����" �� ����� ����!��" �������$ %���"��� ���� ����� �� ����#� ���� cds �� � !��� ���� !��"����� ��� 〈T 〉$

����������� ���� �������

������ �������� �� ��7���� ������ �� � "��� T � �� �� ������� �#� τ ��� �����# N �������� ���� ��� "��� ���� !��" ����� cds��� 〈T 〉 �$�$ T ∼= CRGcds(N )$

+ ���� �������������� �� � � �� ���� ���� N �� !���$ +� ���� � !��� τ ��������# ��� ����� ��� �� ���� T ������ �� ��� ���$

=� !��� ������ � ��������� ������ ����" ���� ��� � τ ��� �������� �������� �����# ����� ����� � ��� τ ��� �����#��� � ��������" τ ���"�� ��� ������� �����#$

���������� �� 0�� T ∼= CRGcds(N ) �� τ��� ������ N = (P, T, F, M0)����� �� � �� �� �� p ∈ P � ����� �� �& ���� �� τ������ (σ, η) � T ���� �� �σ(q0) = M0(p) �� �� �� q ∈ Q � α ∈ enbldT (q)!

η(α) =∑t∈T

α(t) · F (p, t) .

����� ��� ���� ������� �����#� ���� ��������� ��� �����#������ -��������� ��� ������ ������ ��� ������� � ������� �������� � ���� ������������#�. �� T �� ���������$ %������� σ(q0) �� η : 〈T 〉 → S �����#���� #�� � #�� σ : Q → Q ���� ���� ∆(σ(q), η(α)) = σ(δ(q, α)) �������α ∈ enbldT (q) �� ���� ���� �����#�� �� #�� � τ ���"� � T $ +� ��#���� ������� ���� � #�� σ$

1� T ∼= CRGcds(N ) -�� ����#���. �� CRGcds(N ) ↪→ CRG(N ) -����!���. ����� ��� �#�����" �� ��� ������ � ������ �� ��������$ F��σ : Q → Q �� ��� #�� ��!�� �� σ(q) = f(q)(p) ����� f(q) �� ��� �#�"� � q����"� ��� ��#�����# ∼= -���� f(q) �� � #����" � N .$ F�� η : 〈T 〉 → S �� �������� � ��� �������$ + ���� � ��!��� 3 σ �����!�� η(α) ∈ enbldτ (σ(q))�� ∆(σ(q), η(α)) = σ(δ(q, α)) ������� α ∈ enbldT (q) �� �� ��� �����!��σ(q0) = M0(p) ������� ∼= �� � ��#�����#$ %�� ������ �������� ����$ ��

=� � �� ������ ��� ������ ������ � ��� ����� ����� �� ����� ��������" #��!���� � ��� �� �� � ���� � ���#B

'� *�+3������� ��+ ��

�� �� � ���� � ���� �������

@� ����� ����� q � T enbldT (q) = enbldT ,τ (q) \ cds(enbldT ,τ (q))$

������� �� T �� �� ��� ��� "T ∼= CRGcds(N ) �� ���� N # �, T � ������ ��������� ����� � �� �� � ���� � ���� ��������

����� -=⇒. F�� f : Q → (P → Q) �� ��� #�� ���� ����������� - ���������#����"�. � ��� ��#�����# T ∼= CRGcds(N )$ =� !��� ������ ����

enbldT ,τ (q) ⊆ enbldN (f(q)) . -3.

+���� ��� α /∈ enbldN (f(q))$ %�� ����� �� � ����� p � N ���� ����

∑t∈T

α(t) · F (p, t) /∈ enbldτ (f(q)(p)) .

F�� (σ, η) �� ��� τ ���"� � T ������ �� p ������" � ������� 3$ %��σ(q) = f(q)(p) �� η(α) =

∑t∈T α(t) · F (p, t) ���� η(α) /∈ enbldτ (σ(q)) ��

� α /∈ enbldT ,τ (q)$% ��� ����� ���� ����� ��� q = r � Q$ %�� f(q) = f(r) � ���� � ���

��#�����# T ∼= CRGcds(N ) ���� f(q)(p) = f(r)(p) �� �#� ����� p ∈ P $F�� (σ, η) �� ��� τ ���"� � T ������ �� p ������" � ������� 3$ %��σ(q) = f(q)(p) �� σ(r) = f(r)(p) ���� σ(q) = σ(r)$

% ��� �� �� � ���� � ���� ������� �� !��� ��� ���� �� ��� α ∈〈T 〉 �� q ∈ QB

α /∈ enbldT (q) ⇒ α /∈ enbldT ,τ (q) \ cds(enbldT ,τ (q)) . -4.

F�� q ∈ Q �� α /∈ enbldT (q)$ + ���� � ��!��� 9 �� ��� ��#�����#T ∼= CRGcds(N ) �� ���� ���� ������B -�. α /∈ enbldN (f(q))6 � -��. α ∈enbldN (f(q)) ∩ cds(enbldN (f(q)))$

+� -�. ���� ��� �� -3. �� ���� α /∈ enbldT ,τ (q) �� � -4. ����$ + -��. ������� ��� �������$ +� α /∈ enbldT ,τ (q) �� ���� -4.6 �������� α ∈ enbldT ,τ (q) ���� ��� ��� �����"B Y = enbldT ,τ (q) �� X = enbldN (f(q))$ ������� X ∈ Xτ

�� �� -3. �� ���� Y ⊆ X $ ������ �� ��!��� 9 �� T ∼= CRGcds(N )�� enbldT (q) ⊆ enbldT ,τ (q) -����� ������ ����. �� ���� X \ cds(X) ⊆ Y $/��� �� ��!��� 5-4. α ∈ cds(X)∩ Y ⊆ cds(enbldT ,τ (q)) �� � -4. ����$% !��� ��� ��� � �� �� � ���� � ���� ������� �� � ��� ���� �� ��� q ∈ QB

enbldT (q) ⊆ enbldT ,τ (q) \ cds(enbldT ,τ (q)) . -5.

H� ��� ��#�����# T ∼= CRGcds(N ) �� ��!��� 9 �� ���� ���� enbldT (q) =enbldN (f(q)) \ cds(enbldN (f(q)))$ /��� enbldT (q) ∩ cds(enbldN (f(q))) = ∅$%��� �� -3. �� ��!��� 5-3. enbldT (q) ∩ cds(enbldT ,τ (q)) = ∅$ ������ �� ���� enbldT (q) ⊆ enbldT ,τ (q) -����� ������ ����. �� � -5. ����$

-⇐=. F�� R �� ��� ��� � ��� τ ���"�� � T $ =� ���� ��� ���� �� T �����!����� ����� ���� ����� �� �� �� � ���� � ���� ������� ��� T ∼=

�$����� �� �� !��� ���� ������ *������ '�

CRGcds(N ) ����� N = (P, T, F, M0) �� ��� τ ��� �����# ��!�� �� P = R M0(p) = σ(q0) �� F (p, t) = η(t) �� �� p = (σ, η) � P �� t � T $ + ����� ��� RMcds(N ) ����� ��� ��� � ��� ��� ��������� #����"� � CRGcds(N ) �� M [α〉〉M ′ ��������� ��� !��" � � ���� � ���� "����$

F�� ∼⊆ Q × RMcds(N ) �� ��� ����� ������ ������" q0 ∼ M0 ���� ����q ∼ M δ(q, α) = q′ �� M [α〉〉M ′ ����� q′ ∼ M ′$

=� ���� !��� ���� ∼ �� � ������� ������� ������ Q �� RMcds(N )$ H��������� M0(p) = σ(q0) �� ����� ����� p = (σ, η) � N $ 1� ��� q ∼ M���� δ(q, α) = q′ �� M [α〉〉M ′ �� ����#� �� ��� ���� � � ������ ����M(p) = σ(q) �� ����� ����� p = (σ, η) � N $ �� (σ, η) �� � τ ���"� � T σ(δ(q, α)) = ∆(σ(q), η(α))$ �� p = (σ, η) �� � ����� � N F (p, t) = η(t) �� ��� t�� �������� � N ����

σ(δ(q, α)) = ∆(M(p),

∑t∈T

α(t) · F (p, t))

.

@�# M [α〉〉M ′ �� ���� ����

M ′(p) = ∆(M(p),

∑t∈T

α(t) · F (p, t))

.

�� � ������ M ′(p) = σ(δ(q, α)) = σ(q′) �� �� ���� q′ ∼ M ′$ * q ∼ M �#�����M(p) = σ(q) �� ����� ����� p = (σ, η) � N $ @� �� q, r ∈ Q �� �����

���� ����� q = r �#����� σ(q) = σ(r) �� �#� τ ���"� (σ, η) � T $ %������� ��� ������ ∼ �� � ������� ������� ������ Q �� RMcds(N )$

E�� ��� ���� �� � ��� ���� ��� �����" �� �����!��B

q ∼ M ⇒ enbldT ,τ (q) = enbldN (M) . -9.

F�� α ∈ enbldT ,τ (q)$ +� ��� ��� ���� ���� �� ����� ����� p = (σ, η) � N M(p) = σ(q) ����� q ∼ M $ @�# ��!��� 4 η(α) ∈ enbld τ (σ(q)) �� ���τ ���"�� (σ, η) � T $ H� �������� � N F (p, t) = η(t) �� ��� t ∈ T ��p = (σ, η)$ /��� η(α) =

∑t∈T α(t) · F (p, t)$ %�������

∑t∈T

α(t) · F (p, t) ∈ enbldτ (M(p))

�� ����� ����� p � N �� � α ∈ enbldN (M) -�� ��!��� 3.$% ��� ��� ������� ������ ��� α ∈ enbldN (M)$ %�� �� ��!��� 3

∑t∈T

α(t) · F (p, t) ∈ enbldτ (M(p))

�� ����� ����� p � N $ @�# ��� �������� � N �� ����� ���� F (p, t) =η(t) �� ��� t ∈ T �� p = (σ, η) ���� η(α) ∈ enbld τ (M(p))$ @� ����� �����p = (σ, η) � N M(p) = σ(q) ��� q ∼ M $ * η(α) ∈ enbldτ (σ(q)) �� �����τ ���"� � T $ /��� �� ��!��� 4 α ∈ enbldT ,τ (q)$

'5 *�+3������� ��+ ��

=� � ������ ���� q ∼ M �#����� enbldT (q) = enbldN ,cds(M) ���������� ��# -9. �� �� � ���� � ���� ������� ��

enbldN ,cds(M) = enbldN (M) \ cds(enbldN (M)) .

/��� ∼ �� � ������� ������ Q �� RMcds(N ) �� � T ∼= CRGcds(N )$ ��

+ #�� ������ � ��������� ��������� ��� "����� ����� � ���� !��"������� #�� �� ����������� � !��" ������� ������ �� �������� �����$ +���� ���������� ���� ��� ����������� �����# #�� �� �������� �� �����$

����������� ���� � �� �� �

D��� � ������� � ����� ������ �������� �� ��7���� �������� � "��� T � �� �������� �� �#� τ ��� �����# N ���� ���� � �������� ������� �$�$�$N ��N �� �������� ���� ��� ���� !��" ����������� �� �$

%�� �����" ����� ���#� � ������ � ����� ���� ����� ������ ������ � ��� ���� �����#B

����������

@� ����� ����� q � T �� ��� α, β � enbldT (q) �� α � β ��� β � α$

���� �����������

@� ����� ����� q � T �� ����� �!��� ���� � ����� α1 ≺ . . . ≺αi ≺ . . . � 〈T 〉 ����� �� � τ ���"� (σ, η) � T �� i ≥ 1 ���� ����η(αi) /∈ enbldτ (σ(q))$

�� �� � ���� � ���� � �� �� �

@� ����� ����� q � T �� ����� ���� α � 〈T 〉 \ enbldT (q) ����� ��� τ ���"� (σ, η) � T ���� ���� η(α) /∈ enbldτ (σ(q)) � ����� �� β ∈enbldT (q) ���� ���� α ≺ β$

F�� �� #��� �#� ��#���� �� ���� �����������$ @� #�� ������� ���� ������" �$"$ ��� ���#����� ��� ���� ���# �� �����0��� ���� ��������� 〈T 〉 �� ������ ������� �$�$�$ �� τ ��� �����#$ %�� ��� � ��������������� �� � �������� ��� ������� �����" � � �!��� ���� � �����α1 ≺ . . . ≺ αi ≺ . . . �� �#� ��������� #����" � ��� ���������� �� ����������� ���� ������ � ���� �������" ��� � ���#$ *��� !��" ������� ���� ���������� ���� ������I

! ����������� �� ���� ������� �������� ����� �

=� !���� ������ ��� ���������� ���� � ��� �������� �����# �� τ ���� �������� !��" �������B

������� ���� ����� ���� ����� �������

D��� � !��� T �� � ���� !��" ����� cds ��� 〈T 〉 ������� � !���τ ��� �����# N ���� ���� T ∼= CRGcds(N )$

�$����� �� �� !��� ���� ������ *������ '(

@� � !��� ������� τ � �� ������ ������ �� ���������� ��#����� �τ ���"�� ��� ���� �� ���� ��7����$ @� ���#����� ��� ���� ��������� ���"����#�� ������� ����� ��� ���#���� �������������� � %����# ' ������ �������� ��� ����� �#� ��� ���� � �� �� � �#���� ��� �7�����$ @��%���� ���� ��� #���#�� ���� !��" ����� -������ ��# #������� ������. �� ��7��� � ����� T �� ��� � &�� ���� ���# �� ��� � ����� ��� ����������"����# ��!�� � &3) -�� ��������� ���� !��".$

1� ������ � �#���" � !��� !��" ����� cds � #�� ������ � �������� ���� CDS � ���� !��" ������� � ���� � ����" ��� �����" �����#B

������� ���� ����� ���� ������� �������

D��� � !��� T �� � ��#��� CDS � ���� !��" ������� ��� 〈T 〉 ������� � !��� τ ��� �����# N �� ������ cds � CDS ���� ����T ∼= CRGcds(N )$

�"�� �� !��� �������� τ �� !��� ��#����� � ���� !��" ������� CDS ��� ������ ������ �� ���������� ��#����� ��� � �� �#���#�� � #���������$ + ���� � ������ ���� ����# �� ����� � ��� ���� � ���� ����� ������� �� �������� ��"����# �� �%���� ���� ���� !��" ������� ��#�" ��#���#���" ����� ������� � ����� ����� !��" ��� ������ � ��� ���#������������� �� ���� � ��� �������� �����#$

� �������� ������ #��� ������ ��#�� �� ���� �� ������� ��"��� �%���� #�� �� ��� �� τPT ���� �� ��� ������� ������������ "����CRG(N )� � �%��� �����# N ������� ��� ���� CRGcds=(N ) ����� cds= �� ��� ����!��" ����� ������ ��# ��� � ������ � �����$ E�� "�� �� � ������ � ������ ��� �����" �����!� ������ � ��� �� �������� �����#B

����������� ���� ������� ��� ��

������ �������� �� ��7���� ������ �� � "��� T � �� ���������� �#� PT ��� �����# N ���� ��� ���� !��" ����� ������ �� �#������� #�� $ : T → Z �� ��!�� � <��#��� ( �$�$ T ∼= CRGcds�$

(N )$

������� ���� ����� ���� ������� ��� ��

D��� � !��� T ������� � !��� PT ��� �����# N �� � ������ #��$ : T → Z ���� ���� T ∼= CRGcds�$

(N )$

/����� ��� �����#�� � ��� ���� �����#� �� � ������ ������ �� ���������� ������� ��!�� ��# ������ #��� ��� "������� � ������ ��������� ��� �%����$ %��� ��7����� #�� �� �#���� ���� �� ������" ��!��� 5 ������� ' �� %����# ' �� �����$

��������� $ ���%�� ��� ����� ����� �� � ����� ���� !��" ����� ��τ���� ���� 〈T 〉 �� � ���� cds : 2〈T 〉 → 2〈T 〉 ���� �� �� �� �� X ⊆ 〈T 〉 �Y ⊆ X!

'� cds(X) ⊆ X/

'7 *�+3������� ��+ ��

(� X ����� ⇒ cds(X) = ∅*� X ���� ⇒ cds(Y ) ⊆ cds(X)�+� X ∈ Xτ � X \ cds(X) ⊆ Y ����� cds(X) ∩ Y ⊆ cds(Y )�

��������� &� ���� �������� ��� ��� � � 〈T 〉� ��� cdsb� : 2〈T 〉 → 2〈T 〉 �� ���

� � ���� �� � cdsb�(X) = ∅ � X �� ����� � ��������� cdsb

�(X) = {α ∈ X |(∃β ∈ X) α ≺ β}�

���������� � 3 � �� �������� � 〈T 〉� ��� cdsb� �� ������ ���� ����

������ ���� 〈T 〉�

������� �� 0�� T �� ���� � cds �� ������ ���� ���� ������ �� 〈T 〉���� T ∼= CRGcds(N ) �� ���� τ��� ������ N �, T � ������ ����� ���� ��

���� � �� �� � ���� � ���� ��������

%�� ����� �����# �� ��� � ���� �� ��� �����"B "��� � !��� T ������������� ����� ������ �� ������� � !��� PT ��� �����# N �� � ������ #��$ : T → Z ���� ���� T ∼= CRGcds(N ) �� cds = cdsb

�$$ + ���� � ������ �

������ �� �������� �������� ��# ��� ���#���� �������������� ��������� %����# 3 � ���� � �#���� � �,������ ����������� � ��� ��� � ���τPT ���"�� � T $ %��� �� �� �� �� �����$

@���� � �������� � ����" ���� �� T = (Q, S, δ, q0) �$�$ � ������������� ������� �����# Tr = (Q, S, δ′, q0) ���� ���� �� ��� q ∈ Q �� α ∈ 〈T 〉 δ′(q, α) = δ(q, α) � �� �� ���!�� �� δ′(q, α) = δ′(q′, α′) ������ q = q′ ��α = α′$ %�� �������� ���� q

α−→ q′ � T \Tr -���� ���� δ(q, α) = q′ �� δ′(q, α) �����!��. ��� ������ �����$ <��� ���� q

α−→ q′ �����#��� � ����� ����� � T �������$ F�� q′′ �� ��� ������ �## ������ � q �� q′ � ��� ����" ����Tr ��� ��� ���� ��# q′′ � q ��� ���� q

α−→ q′ �� ��� ������� ���� ��# q′ �q′′ ��# � ����� � T $ %�� ����� � ���� ����� �� � �� ���� sign1(α1) . . . signn(αn)����� ��� αi ��� ����� �� ��� ��"� -+ � −. �����"���� ������ ��� �������� ��� ������� ����$

@�# ��!��� 4 �� �� ������" ���� T �� ��������� � τ ���"� (σ, η) � T�� ������ �����#��� �� σ(q0) �� ��� #�� η ����� �� �����#��� � ��� �� ��������� η(t) �� ��� t ∈ T $ + ��� ���� � τPT ���"�� σ(q0) ∈ N �� η(t) ∈ N × N

�� ��� t$ *����� ���� �� ���� ��������� pinit �� t•p �� p•t �� ��� t ∈ T $ �τPT ���"� (σ, η) � T #�� �� ���������� �� � ��"����� ���"�� �������� ����� ��������� ���$ σ(q0) = pinit �� η(t) = (p•t, t•p) �� ��� t$ �������� � ���� ���� � ��"����� ���"�� ������� � ��� ��������� pinit t•p �� p•t���� ��!� � τPT ���"� � T �� �� ����� �� � ��4���� ����B -�. �� ��������� ����� sign1(α1) . . . signn(αn) �� ����B

∑i

∑t∈T

(signi(αi(t))) · (t•p − p•t) = 0 ;

�� -��. �� ���� ���� ��# q0 � q �������� ���� α1 . . . αn � ��� ����" ���� �� �� ���� β ���� ���� δ(q, β) �� ��!�� � T �� ����B

pinit +∑

i

∑t∈T

αi(t) · (t•p − p•t) ≥∑t∈T

β(t) · p•t .

�$����� �� �� !��� ���� ������ *������ '8

F�� R ���� ��� !��� �����# ��#�� ��# ����� ����� ��������$ %���� �������� � R "������� ���� η(enbldT (q)) ⊆ enbldτ (σ(q)) ����#�" ����

σ(q) = pinit +∑

i

∑t∈T

αi(t) · (t•p − p•t) .

%�� � ����� � R "������� ���� ��� ���� ��!��� � σ �� �#������� ������� �#������ �������� ������ ��# ��� ����� q

α−→ q′ -�$�$ δ(q, α) = q′.B

σ(q′) = σ(q) +∑t∈T

α(t) · (t•p − p•t) .

1� ������" ����� ���� ����� �� �� ������� ������ q �� r ������� ��#q0 �� ����� ���� ���������� ������ α1 . . . αn �� β1 . . . βm � ��� ����" ����Tr �#��� � ������" ������� ����� ������ � ����� -��"�. p ���� ����

∑i

∑t∈T

αi(t) · (t•p − p•t) =∑

j

∑t∈T

βj(t) · (t•p − p•t) .

%��� �� �� ������� ����� ��#� ���#��� � ��� ���� � R$

������" �� �� � ���� � ���� ������� �� �#����� #�� �#������������ ��� � ��� ��� ����� enbldT (q) = enbldT ,τ (q) \ cds(enbldT ,τ (q))����� �� ��� ����� ��� � τPT ���"�� � T �� ��� ���� ��� cds =cdsb

�$������ � ��� #�� $ : T → Z$ @�������� ��� ���� enbldT ,τ (q)

��� !��� ���� ��� ������� ���� cdsb�$

(X) = ∅ �� �� �!��� ��� X �� �� �����# �� ���� #�� �� �#����� ��# � ���� ��� R � τPT ���"�� � T $

%�� !��� ����# #�� �� �����!�� ������$ @� ���� t ∈ T ��� degree(t) �� ���#���#�# � α(t) �� ��� ����� α ���� ���� δ(q, α) �� ��!�� �� �#� q ∈ Q-���� � #���#�# ������ ���� T �� !���.$ %�� �� ���� t pinit = degree(t) t•p = p•t = 1 �� t′•p = p•t′ = 0 �� t′ = t ��!�� � τPT ���"� � T $ %������� ���� α ���� α(t) > degree(t) ���"� � enbldT ,τ (q) �� �� q ∈ Q$

=� ��������� � ��� ���� ����#$ �� ��� � ����� �� �� �������� � R��� ����� �� �#"���� -����� ����� ���# �� ������ 0. ��� ��� � ������������ � ���� !��� �����# ��#� � ��������� �� � Q2|T |+1$ �� ����������� ��� � !��� ��� � "������" ���� -��� &'G). �� ���� ��� �� �� �#����� &()$F�� {pj | j = 1 . . .m} �� ��� ��� � "������" ���� � ��� �� ��!�� �� R ����� ���� ��� pj �� "��� �� � ��"����� ���"�� ����� pinit

j �� �� ��"����� ���"�� #��� pj

•, •pj : T → N$ <��� ��� pj ��������� � ��������"τPT ���"� (σj , ηj) � T $ *��� ��� pj "������ ��� ������ � R �� ����τPT ���"� � T �� � ����� �#����� (σ, η) =

∑mj=1 rj · (σj , ηj) � "������"

��"�� ���� ��"����� ������ ��7����� rj $

F�� q ∈ Q �� ��� α1 . . . αn ����� ��� ���� ��# q0 � q � ��� ����" ����$� ���� α ��� � ���" � enbldT ,τ (q) ��

pinit +∑

i

∑t∈T

αi(t) · (t•p − p•t) <∑t∈T

α(t) · p•t

�� *�+3������� ��+ ��

�� �#� -��"�����. ���"�� ����� � ��� ����� �����# R$ *����� ������ ������ ���� ��

pinit =m∑

j=1

rj · pinitj �� p•t =

m∑j=1

rj · pj•t �� t•p =

m∑j=1

rj · t•pj

����� ��� rj ��� ��"����� ������ ��7�����$ %�� ����������

pinitj +

∑i

∑t∈T

αi(t) · (t•pj − pj•t) <

∑t∈T

α(t) · pj•t

�� �#� j$ %������� ��� !��� ���� � ������ ����� enbldT ,τ (q) �� �� �#�������# ��� !��� ��� � τPT ���"�� R = {(σj , ηj) | 1 ≤ j ≤ m}$

%�� ���� �����# �� ��� ����" �� � ����� ������� enbldT (q) = enbldT ,τ (q)\cds(enbldT ,τ (q)) �� ��� q �� �� �#� ����� ���� !��" ����� cdsb

�$ ��

����� �� � ������ #�� $ : T → Z ��� �� �� ���������$ >����� ���� �� !���� X cdsb

�(X) = {α ∈ X | (∃β ∈ X) α ≺ β} enbldT (q) ⊆ enbldT ,τ (q) �� enbldT ,τ (q) �� !��� �� ��� q$ ������" �� �� � ���� � ���� �������

�#��� �������� � ������" �� ��� �������� � � #�� $ : T → Z ���� ������ ��� q ∈ Q α, β ∈ enbldT (q) �� γ ∈ enbldT ,τ (q) \ enbldT (q)B

∑t∈T

α(t) · $(t) =∑t∈T

β(t) · $(t) ��∑t∈T

γ(t) · $(t) <∑t∈T

β(t) · $(t) .

*��� ��� ���� enbldT ,τ (q) \ enbldT (q) ��� !��� �� �,�������� �#������� ������ � ��� ���� ����� �#"���� � ����� �� �� �������� � ��� ���������$(t) �� !��� �� � �� ������ ������� ����� ������ �� �#���� � �����#�� $ : T → Z$ ���"����� �� ���� ����������� ��� �����" ������$

������� � ��� ������� � ���� ��� ������� �� ���� ���� T ����� �� ���� PT ��� ������ N � � � $ : T → Z ���� �� � T ∼= CRGcdsb

�$(N ) ��

����� ����

������ ��� ��� �����# �� �������� � �� ������� ��# ��� �������������� � !��� �%��� N = (P, T, F, M0) ���� ���� T ∼= CRGcdsb

�$(N )

����� $ : T → Z �� ��� ����� #�� �#����� � ��� ����$ +� ��7��� ��������� � ��� P = {p1, . . . , pm} �� ��� ��� � "������" ���� � ��� �� ���!�� �� R �� � ��� M0(pj) = pinit

j �� F (pj , t) = (pj•t, t•pj) �� ��� t$

%�� ��� � ������ P � N ��������� ��� ��� � "������" τPT ���"�� R ={(σj , ηj) | 1 ≤ j ≤ m}$ +� �� ������ ��� ���� �� ������ q �� r � T ��� ���������� �� �#� τPT ���"� � T �� ���� ��� ��������� �� �#� ��"� � R$%������� �� T �����!�� ����� ���� ����� ��� #�� φ ���� ���� � ����� q ���� #����" ��!�� �� M(pj) = σj(q) -1 ≤ j ≤ m. �#���� T �� CRG(N )� ���� � ��� ���� enbldT (q) ⊆ enbldT ,τ (q) = enbldCRG(N )(φ(q)) �� ��� q$ ��T �����!�� �� �� � ���� � ���� ������� �� ����� ��# ��!��� 9 ����enbldCRG

cdsb�$

(N )(φ(q)) = enbldT (q) �� ��� q$ /��� T ∼= CRGcdsb�$

(N ) ��

�� �����$ *�##�" �� � �� ����� ��� �����" ������$

�$����� �� �� !��� ���� ������ *������ �'

������� !� ��� ������� ���� ����� ������� � � ������� �� ������ ���� ������� ��� �� � ������

" ������ #��

H� ���" �� ������" ������ � �#� ����� ������ �����" ����� ������� ���� !��" ������� ���� ����� ��� ���� �� � �� ��������� ��������������� ������� � ��������� �#������$ �#" �##������ ������ ����� ������ � ��� ��������� ���� � ���� ������ �� ���B

� � �������������� � ��� �������� ������ �� ����� �� ���� !��" �������$� � ������!���� � ���� !��" ������� ������" � ����� ��������� �#����

#��������� -� ���� �����#���� ������� ��� ����� ��# <��#��� A.$� *������� ��# ���������� ������������ ���� ��� !��� ���� �������

�����#� -�$"$ ��# ��"��"�� ��������" � �!��� ������� �����#�.$� ���#�� ���� !��" ������� ����� ��� ����� ������� ������ ��� ����

��� �� #����" -�� � �� �� � ���� ���� ����� � ��� ���� � �%��������#� �� ������ ������ ���� #����" ������� ������� ����� ����!�����.$ 1�� ���� ���#�� ������� ���� ���#� � �#����� ����������� �� ���������� � ��� ����� ���� �� �����#����� �� ��#��� -�����#��� ������� ������� �� �� ������ � ��� ������ �����.$

� F������ ���� !��" ������� ����� � ������� �� ��� ������ #����" ��� �����" � � ���� �� ����� ������" �#� ������� ������ ���������$=����� ���� ���� ������� ��� � �� ������� ���� ���� �� � ��������� ��������� �� ������ ���������� -�� ���#��� ������� ������� �� ������������� ���� �� ���� �� � �����.$ /����� ����� ����� �������������� ���� �� ��������"$

@����� �� �� ��������� ����� ����" ���� ����� ��� �� � ��"�������� �� #�����#� ����� � �� ��������"�� ����� ���� �� ����� ������� �"����� �������������� � ���������� ������� �����#� � ��� ���� � ����� ������� ���� !��" �������$

�������������� =� ��� "������� � ��� �������� �� ����� �� ������������ � ��� !��� ����� � ���� �����$

����������

'+ &+ ������ 9+ ������������ ��� *�+3�������: *��$������ ��������� ��� ����$����� �� ����� ��+ *���+ %�*�6�%;8�� *+3+<��� <+ ����� ���<+�+���!���=-��� >��+?� �������� 9 �� ��� >'88�? �5�@�(7

�+ &+ ����� ��� *�+3�������: 6� ��� �$����� �� A������ *���� ��+ ������� ������ ���� >'885?

�+ &+ ����� ��� *�+3�������: %����$ �� ������+ 9����� �� *���� �� �: ���<����� 1+����� ��� A+��=��-��� >��+?� �������� 9 �� ���� >'887? ��8@�75

�� *�+3������� ��+ ��

�+ 9+ ������������� A+3� <������� )+*����� ��� �+B����: 6� ��� �$�������� �������� �� %�������� �$���+ �� ���������� �� ��������� � ���� C+3��� >��+?��������� >'885? ''@�'

�+ + � ��� A+<+*����: �$����� �� �� !��� ����-���� ���+ *���+ �6 �"�;8(��+<�=�0��!��= ��� C+1��0�!0� >��+?� �������� 9 �� ���� >'88(? '�'@'5�

5+ +������0�#�: ��������� ��� ������� � A������ ������ ��� ��� ���������#� �������� �� � �$��� �� 9����� ���,������+ ���� ���������� ��� ������� ���

��� �������� � ����� � >'85�? ��7@���(+ C+����������� <+)�����#0$� �+)������$�#� 9+9�#���� ��� �+D�0�#��#: *�����$:� ���� ��� ����������� ��������� ����/������ ��� $����� �� �$�����������������+ ���� ������ � ��������� ��� ������� ����� >'88(? �'�@���

7+ C+3��� ��� 1+�����: %�� �$����� *��-��� �� *���� ��+ ���� ���������� ��

>'885? �8(@�'�8+ �+&��������� ��� A+��=��-���: *������ >���? ���������2 ���� �� ��� �������� ��� ������������� *��-���+ ���� ���������� �� >'88�? �'�@���

'�+ �+&��������� ��� A+��=��-���: *������ >���? ���������2 ���� ��� ����� ������� ��������� �$���+ ���� ���������� �� >'88�? ���@�57

''+ � �: ���������������� ���������������� ����������� �

'�+ C+)���E�� <+)���$ ��� A+��=��-���: %�!��� � *���� �� �������� ��� <���-���� �$���+ *���+ 1<�;��� �+������ A�+*��� A+��=��-��� ��� �+�������>��+?� �������� 9 �� ���� >���5? �8�@��8

'�+ <+)���$ ��� <+*���0��!��=�)���$: %�������� �$��� �� &��������$ �� �$���� !��� 9��������+ *���+ �6 �"�;�5� �+ ���� ��� F+F������ >��+?� ��������9 �� ���� >���5? '(�@'7(

'�+ <+)���$ ��� <+*���0��!��=�)���$: �$����� �� &��������$ �� �$��� !���������� ��� ��� 9��������+ *���+ ���%* ;�(� C+)���E� ��� �+D�0�#��# >��+?�������� 9 �� ���� >���(? �7'@���

'�+ �+<�=�0��!��=: *���� �� 1����� %�0��+ *���+ ���%* ;�(� C+)���E� ����+D�0�#��# >��+? �������� 9 �� ���� >���(? ��@��

'5+ <+<0��: *���� �� ��� ���� %�������� �$���+ ������������ ������ �

��������� � ������ �������� � >'88�? ���@�(7'(+ <+*���0��!��=�)���$: %�� �$����� *��-��� ��� &��������$ �� !��� ����-����

���+ ���������� ����������� �� >'888? ��'@�7�'7+ �+�����E#��: � ��� � ������ ��� ���� �� �� ������ + C��� 1���$ >'875?'8+ *+����0�: ���� *�������� �� %���� �� ���� ��� &������ ������ ���+ ��: ���

#���� �� *���� �� '878� �������� 9 �� ��� >'88�? �'7@���


Recommended