Generalized State Classes of Time Petri Nets for Timeliness Analysis

格式：pdf
大小：91.47 KB
文档页数：15

Generalized State Classes of Time Petri Nets for Timeliness AnalysisD IANXIANG X U+*, J IACUN W ANG++ AND R ICHARD A. V OLZ++Department of Computer ScienceTexas A&M UniversityCollege Station, TX 77840, USA++Nortel Networks2201 Lakeside Blvd, MS-99203G50Richardson, TX 75082, USASubmitted as a short paper to IEEE Transactions on Robotics and Automation Special issue on Analysis and Control of Automated Manufacturing Systems via Timed Petri-Net Models.A BSTRACTTime Petri Nets (TPN’s), as an expressive formalism for modeling distributed real-time systems, are usually analyzed through classical state classes or clock-stamped state classes. There are two issues, however, that have not been effectively or efficiently addressed: 1) how to facilitate the timeliness analysis, particularly the end-to-end time delay of task execution, and 2) how to compare state classes for equality in order to reduce state space. In the state class approach, dynamic firing domains consisting of relative firing intervals of individual transitions and timing inequalities for pairs of transitions have to be transformed into a canonical form, which has polynomial complexity. This makes the generation of state class graphs more complicated and the computation of end-to-end delay of task execution inconvenient. In the clock-stamped state class approach, the conditions for determining the fireability of transitions in general TPN’s are loosened indirectly because of the use of global firing domains, which may lead to a bigger reachable set than that obtained by using the state class approach, and only state class trees, rather than graphs, can be generated. To solve these problems, this paper uses dynamic, relative firing intervals for the determination of transition fireability and global firing domains for the timeliness analysis. For general reachability analysis, a state class graph is generated only in terms of relative firing intervals. Whenever a goal is reached through a certain schedule, global firing domains are applied to analyze the end-to-end delay of the schedule. A simple yet typical manufacturing system is used to demonstrate our approach.Keywords: Time Petri nets, state class, reachability analysis, timeliness analysis, real-time systems.* Corresponding author: Dianxiang Xu, xudian@.I. I NTRODUCTIONPetri nets [1, 2] have been used to model a variety of discrete event systems [3, 4] due to their power in modeling asynchronous events, parallelism, contention, and synchronization. It has been of high interest to extend and use Petri nets by adding time features for time dependent systems [5]. Introduction of time into transitions, places or arcs increases the modeling power as well as the complexity of net analysis. Several extended models of Petri nets have been proposed to deal with the timing issues [6], such as timed Petri nets [7, 8], stochastic timed Petri nets [9], and time Petri nets (TPN’s) [10]. Among these models, TPN’s are most widely used for real-time system specification and verification [5, 11-13]. In TPN’s, event synchronization is represented in terms of a set of pre- and post-conditions associated with each individual action of the modeled system, and timing constraints are expressed in terms of minimum and maximum amount of time elapsing between the enabling and the execution of each action. This allows for explicit modeling of time-dependent concurrency and parallelism. It has been shown [5] TPN’s are expressive for most of the temporal constraints while some of these constraints are difficult to represent only in terms of durations, e.g. in Ramchandani’s Timed Petri nets [8].The most fundamental and useful method for analyzing TPN’s, like for many other formal models, is reachability analysis [5]. It permits the automatic translation of behavioral models into a state transition graph made up of a set of states, a set of actions, and a succession relation associating states through actions [11]. The state transition graph makes explicit such properties as deadlock and reachability [14], and allows for the automatic verification of ordering relationships among task execution times [12]. Two major approaches for the reachability analysis of TPN models are classical state classes [5] and clock-stamped state classes [13]. As will be discussed in detail, however, there are two issues that these approaches have not effectively or efficiently addressed: 1) how to facilitate the timeliness analysis, particularly the end-to-end time delay of task execution, and 2) how to compare state classes for equality in order to reduce state space when generating a state class graph. These issues are important for practical analysis of distributed real-time system models.In the classical state class approach [5], timing inequalities representing the relationships among the firing times of transitions are introduced in dynamic firing domains regarding the fact that relative, dynamic firing intervals of individual transitions alone are inaccurate for timeliness analysis. Accordingly, the timing inequalities for transition pairs, although independent of the determination of transition fireability under a given state class, are also considered for the comparison of state classes (i.e. whether or not two state classes are equal depends on their markings, dynamic firing intervals as well as the inequalities). To do so, dynamic firing domains have to be transformed into a canonical form, which has polynomial complexity [5, 11]. In general, the inequalities make the generation of state class graphsmore complicated. So, this approach is inefficient in deriving the end-to-end delay of a task schedule. In contrast, the clock-stamped state class approach [13] uses the global time mode for state classes, and the end-to-end delay can be easily obtained. Since two schedules reaching the same marking generally have different global time delays, this approach does not compare clock-stamped state classes for equality and thus only generates state class trees, rather than state class graphs. As a result, the reachability analysis is less efficient due to the increased complexity of state space. Another critical problem with the clock-stamped state class approach is that it loosens the conditions of determining the fireability of transitions because of the use of global firing domains. As a consequence, it makes some unreachable markings reachable in some cases. Therefore, this approach is not quite suitable for the timeliness analysis either.To solve the above problems, this paper presents an effective approach, using relative firing intervals for the determination of transition fireability and global firing domains for the timeliness analysis. For reachability analysis of a general TPN model, we generate the state class graph only in terms of dynamic firing intervals of individual transitions without considering the timing inequalities on transition pairs. Whenever a goal is reached through a certain schedule in the state class graph, global firing domains are applied to analyze the end-to-end delay of the schedule. A simple yet typical manufacturing system will be used to demonstrate our approach.The rest of this paper is organized as follows. To make the paper self-contained, section 2 gives a brief introduction to TPN’s, state classes, and clock stamped state classes, and describes the problems with the two approaches. In section 3, generalized state classes are introduced for the reachability and timeliness analysis of TPN’s. Section 4 presents the modeling and analysis of a simple manufacturing system. Section 5 concludes this paper.II. T IME P ETRI NETS, S TATE C LASSES AND C LOCK-S TAMPED S TATE C LASSES In this section, we first define TPN’s that will be used, then briefly review state classes and clock-stamped classes and analyze the issues that they have not efficiently or effectively addressed.A. Time Petri NetsA TPN is a tuple (P, T, B, F, M0, SI) where:(1) P = {p1, p2, …, p m} is a finite nonempty set of places.(2) T = {t1, t2, …, t n}is a finite nonempty set of transitions.(3) B: P × T → N is the backward incidence function.(4) F: T × P → N is the forward incidence function.(5) M0 is the initial marking. (P, T, B, F and M0 together define a Petri net)(6) SI is a mapping of static intervals. ∀t ∈T, SI(t) = [SEFT(t), SLFT(t)], where SEFT(t) andSLFT(t) are non-negative rational numbers, SEFT(t) is the static earliest firing time, and SLFT(t) is the static latest firing time.A state of a TPN is a pair S = (M, I) consisting of a marking M and a firing interval set I. I is a vector of firing times.The number of entries in this vector is given by the number of the transitions enabled by M. A state is reached from the initial state by a given sequence of firing times corresponding to a firing sequence. Since any reachable marking may be reached from the initial marking by different sequence of firing times corresponding to the same firing sequence, the state space is generally infinite.B. State ClassesA state class of a TPN, as an aggregated pseudo-state associated with a firing sequence, represents all states reachable from the initial state by firing all feasible firing values corresponding to the same firing sequence [5]. Let Enabled(M) be the set of transitions enabled under marking M, and τ(t) be the firing time of t relative to the time point when M is reached. A state class is a pair C = (M, D), in which M is the marking of all states in the class, and D is the firing domain defined as a set of linear inequalities. For clarity, we classify the linear inequalities into two categories: the dynamic firing intervals of individual enabled transitions (i.e. a i≤τ(t i) ≤ b i, for any t i∈ Enabled(M) ) and the inequalities of timing constraints on pairs of enabled transitions (i.e. a ij≤τ(t i)- τ(t j) ≤ b ij for any t i, t j∈ Enabled(M) and t i≠t j). Note that, whether or not a transition enabled by M is firable under state class (M, D) depends on the dynamic firing intervals. The inequalities are in essence used for the timeliness analysis and the comparison of state classes when the state class graph is generated. In order to make use of dynamic firing domains, they need to be reduced into a canonical form. It has been proven that one such canonical representation exists uniquely, and an algorithm for this purpose has polynomial complexity [5, 11]. [11] shows timeliness analysis can be conducted by repetitive exploration of the firing intervals and inequalities in the state classes. In comparison, we will show it can be achieved in a more convenient and effective way by using global firing intervals. The generation of state class graph is then made more efficient because there is no need to consider the inequalities in state classes.Without considering the inequalities, we denote a dynamic firing domain D as {D(t)= [EFT(t), LFT(t)]: t∈Enabled(M)}, where D(t) is the dynamic firing interval of t, and EFT(t) and LFT(t) are the dynamic earliest firing time and latest firing time of t, respectively. An enabled transition t is firable under state class C if EFT (t) ≤min{LFT(t i), t i∈Enabled(M)}. Suppose Firable(C) is the set of firable transitions under state class C, and MLFT(C) = min {LFT(t i), t i∈ Firable(C)}is the minimum of latest firing times of all firable transitions in Firable(C). The construction of the state class graph of TPN can be briefly outlined as follows: The initial state class is C0 =(M0, D0), where M0 is the initial marking and D0= {[SEFT(t), SLFT(t)]: t∈Enabled(M0) } (at the initial state, the dynamic firing interval for any enabled transition is equal to its static firing interval); Given a state class C k= (M k, D k), a successor state class C k+1= (M k+1, D k+1) can be created for some t ∈ Firable(C k) by following steps:• The actual firing interval for t under class C k is [EFT k(t), MLFT k(t)]. M k+1 is obstained according to the firing rule of classical Petri nets.• For each inherited transition t j (t j≠t) that is enabled under both M k and M k+1, EFT k+1(t j) = max(0, EFT k(t j)-MLFT(C k)), and LFT k+1(t j) = LFT k(t j)-EFT k(t)• For each newly enabled transition t j under M k+1 (not enabled under M k), EFT k+1(t j) = SEFT(t j) and LFT k+1(t j) = SLFT k(t j).Note that, dynamic firing intervals of individual transitions alone are inaccurate for the timeliness analysis. For example, suppose the initial marking for the TPN in Fig. 1 is (1, 0, 1, 0. 0)T. According to the semantics of TPN’s, the correct time span for reaching marking (0, 1, 0, 1, 0)T by firing t2 and t1 is [3, 5]. Using the state class method, the relative firing intervals for t1 after t2 fires at sometime during [2, 4] is [max{0, 3-4}, 5-2], i.e. [0, 3]. Obviously, the intervals [2, 4] and [0, 3] have no clear relationship with the correct time span [3, 5].C. Clock-Stamped State ClassesA clock-stamped class [13] of a TPN consists of three parts: 1) a marking M, 2) an "global" firing domain corresponding to firing intervals (relative to the beginning of execution) of all firable transitions in the state class, and 3) a clock stamp that corresponds to the moment when the state class is reached with the clock value relative to the beginning of execution.Fig 1. A TPN ExampleThe clock stamped state class method has two critical issues. First, the fireability of transitions under a clock stamped state class cannot be correctly determined in terms of the global firing intervals. For the above example, when marking (0, 1, 0, 1, 0)T is reached, the time stamp for the state class is [3, 5], andthe firing domains for newly enabled transitions t3 and t4 are [1, 3] + [3, 5] = [4, 8] and [4, 5] + [3, 5] = [7, 10], respectively. According to the firing rules of clock stamped state classes, both t3 and t4 are firable because both EFT(t3) = 4 and EFT(t4) = 7 are less than min{LFT(t3), LFT(t4)} = 8. This is incorrect regarding the semantics of TPN’s due to the fact that t4is never firable (t3must fire before t4, which disables t4). In essence, clock stamped state classes are not suitable for the reachability analysis of general TPN’s. Second, since time stamps in a firing schedule are increasing monotonically, the clock stamped state class method can only generate state class trees, rather than state class graphs. This makes state space even more complex.III. T IMELINESS AND R EACHABILITY A NALYSISIn this section, we generalize the concept of state classes by integrating classical state classes with global time mode for the timeliness analysis of TPN’s, such that:• relative firing domains are used to determine the fireability of transitions, and• absolute firing domains are used to calculate the time span of a firing schedule.For general reachability analysis, the state class graph of a TPN is generated only in terms of dynamic firing intervals. The timeliness of a firing schedule is then conducted separately using global firing intervals.A. Generalized State ClassesA generalized state class (GSC) is a 4-tuple C = (M, D, AD, ST) where(1) M is a marking.(2) D is a relative firing domain, i.e., a set of constraints on the values of the time to fire fortransitions enabled by current marking M. For an enabled transition t i, D(t i) represents its relative firing interval. Let EFT(t i) be the left bound of D(t i) (the relative earliest firing time) and LFT(t i) be the right bound of D(t i) (the relative latest firing time).(3) AD is an global (absolute) firing domain, i.e., a set of constraints on the values of the time to firefor transitions enabled by current marking M. For an enabled transition t i, AD(t i) represents its absolute firing interval. Let AEFT(t i) be the left bound of AD(t i) (the absolute earliest firing time) and ALFT(t i) be the right bound of AD(t i) (the absolute latest firing time).(4) ST is the time stamp of the GSC class, which is a (global) time interval.Before we define the transition firing rules, let us explain what we want the absolute firing domain AD and the time stamp ST to be: (1) For an enabled transition t i, AD(t i) gives the global firing time interval of t i, where by “global” we mean the values are counted relative to the beginning of the net’s execution from the initial GSC class C0,defined as C0= (M0, D0, AD0, ST0), where M0 is the initialmarking, D 0 and AD 0 contain all static firing time intervals of the transitions enabled at M 0, and ST 0 = [0, 0]. (2) ST indicates the global time delay interval in which the net runs from the initial GSC class C 0 to current GSC class C. Theorem 1 in next subsection will show this property.Now we consider the firing rules that guide the timeliness analysis of a TPN. An enabled transition t j is said to be firable at GSC-class C k if EFT k (t j ) ≤ min{LFT k (t i ), t i ∈ En(C k )}, where En(C k ) is the set of all enabled transitions at C k . Let Fr(C k ) be the set of firable transitions at GSC class C k , andMLFT(C k ) = min{LFT k (t i ), t i ∈ Fr(C k )},MALFT(C k ) = min{ALFT k (t i ), t i ∈ Fr(C k )},where MLFT(C k ) / MALFT(C k ) define the minimum of relative/absolute latest firing times of all firable transitions in Fr(C k ). We divide the firable transitions in Fr(C k ) into two groups: (1) inherited firable transitions that were firable before C k is reached, and (2) newly firable transitions that begin firable at C k . The firing of transition t f ∈ Fr(C k ) changes GSC class C k to C k+1. Let C k = (M k , D k , AD k , ST k ) and C k+1 = (M k+1, D k+1, AD k+1,ST k+1). We define firing rules as follows:Step 1. Calculate )(~f k t D , the feasible relative firing interval for firing transition t f . It is obtained by shifting right bound of D (t f ) to MLFT (C k ) while keeping its left bound unchanged, that is, )]( ),([ )(~k f k f k C MLFTt EFT t D = LetST k+1 =[AEFT k (t f ), MALFT(C k )]Step 2. Calculate firing intervals of inherited firable transitions in GSC class C k+1.2.1 Let )(1f k k t B M M −′=′+ and collect (inherited) firable transitions at M ′k+1.2.2 Let D k+1 = D k , AD k+1 = AD k and delete from D k+1 and AD k+1 all entries whose correspondingtransitions are disabled by M ′k+1.2.3 For each inherited firable transition t j (t j ≠ t f ) at M ′k+1, letEFT k+1(t j ) = max{0, EFT k (t j )-MLFT(C k )}LFT k+1(t j ) = LFT k (t j )-EFT k (t f )AEFT k+1(t j ) = max{AEFT k (t j ), AEFT k (t f )}.ALFT k+1(t j ) = ALFT k (t j )Step 3. Calculate the firing intervals of newly enabled transitions after firing t f .3.1 Let )(11f k k t F M M +′=++ and collect newly enabled transitions: they are enabled at M k +1 butnot firable at virtual marking M ′k +1.3.2 Add into D k +1, AD k+1 entries for corresponding newly enabled transitions at M k +1: if t j (t j ≠ t f )is a newly enabled transition at M k +1, thenD k+1(t j) = SI(t j).AD k+1(t j) = SI(t j) + ST k+1 .3.3 If t f is still enabled at M k+1 after firing, letD k+1(t f) = SI(t f).AD k+1(t f) = SI(t f) + ST k+1.Note that by Step 3.3, a transition, which is still enabled after its firing, is always treated as a newly enabled one. This simplifies the treatment of states in which a transition has sufficient tokens in its input places to permit multiple firings. The treatment of this situation, usually referred to as multiple enabledness [5], requires multiple firing intervals be associated with a single transition and involves a number of semantic subtleties that are not relevant to the objective of this paper.B. Timeliness AnalysisWe have described the transition firing rules that guide the evolution of GSC classes. Now we show how GSC classes are suitable for timeliness analysis. Theorem 1 illustrates what the absolute firing domain AD and the time stamp ST in a GSC class exactly stand for. Corollary 1 indicates what can be gained from the generation of the reachability graph. To facilitate our description, we denote firing schedule t0 t1…. t n-1 that transforms C0 to C n by (C0, t0)(C1, t1)…(C i, t i)…(C n-1, t n-1)C n.Theorem1. Let C i = (M i, D i, AD i ST i ) be a reachable GSC from C0 = (M0, D0, AD0,,ST0) through firing schedule t0 t1…. t n-1. Then(1) ST i is the global time (interval) when GSC class C i is reached;(2) If t j∈Fr(C i), then AD i(t j) is the global firing time interval of t j.Proof:(1) From the preconditions, we know there must be a firing schedule starting with C0 and ending with C i, that is, (C0, t0)(C1, t1)…(C i-1, t i-1)C i. The proof of the theorem is carried out by induction on i. For the basis case (i = 0), C0 is the initial class. Obviously we have: 1) ∀ t j ∈Fr(C0),. AD0(t j)is exactly the static firing time interval of t j, which is also the global firing time. And 2) ST0 = [0, 0], which is the arriving time of C0. Therefore, the theorem holds for i = 0.Now assume that the assertion holds for i ≤ k. Consider i = k + 1. It follows from the equation ST k+1 = [AEFT k(t k), MALFT(C k)]where AEFT k(t k) is the absolute earliest firing time of t k, and MALFT(C k) is the minimum latest firing time of all firable transitions in Fr(C k), hence the actual latest global firing time of t k. Therefore, ST k+1 is the global firing time interval of t k. Because firing a transition takes no time, ST k+1 is also the global arriving time of state class C k+1, which is reached by firing t k+1. So (1) holds.(2) Suppose that a transition t j is firable at C k+1. There are three different cases of t j.Case 1. t j is a newly enabled transition at M k+1and t j≠t k.AD k+1(t j) = SI(t j) + ST k+1 = [SEFT(t j) + AEFT k(t k), SLFT(t j) + MALFT(C k)],where, AEFT k(t k) is the earliest (global) arriving time of state class C k+1, SEFT(t j) the static (relative) earliest firing time when t j is enabled at C k+1, so SEFT(t j) + AEFT k(t k) is the earliest global firing time of transition t j; MALFT(C k) is the latest (global) arriving time of state class C k+1, SLFT(t j) the static (relative) latest firing time when t j is enabled at C k+1, so SLFT(t j) + MALFT(C k) is the latest global firing time of transition t j. Therefore, AD k+1(t j) is the global firing time interval of t j.Case 2. t j = t k.Because we ignore multiple-enabledness, so t k is viewed as a new enabled transition at M k+1. Thus the conclusion drawn in Case 1 also applies to this case.Case 3. t j is an inherited transition.In this case, it follows from Step 2 thatAD k+1(t j) = [max(AEFT k(t j), AEFT k(t k)), ALFT k(t j)].According to the assumption made for i ≤ k, [AEFT k(t k)), ALFT k(t j)] is the global firing time interval of transition t j at state class C k. The latest global firing time of t j at C k+1 should be the same as it is at C k; however, the earliest global firing time of t j at C k+1 must take the larger value of AEFT k(t j)and AEFT k(t k), because t j is supposed to fire after C k+1 is reached. So, AD k+1(t j) is the global firing time interval of transition t j at state class C k+1.Thus the theorem holds. t According to theorem 1, ST i gives the exact global time interval when GSC class C i is visited. Corollary 1. Let C i = (M i, D i, AD i, ST i) and C j = (M j, D j, AD j, ST j) be two reachable GSC classes of a TPN where C j is reachable from C i. If ∀ t j ∈Fr(C i), t j is a newly enabled transition, then the time span that the TPN runs from C i to C j is ST j −ST i.Proof:Because all firable transitions at C i are newly enabled, so the future behavior of the TPN starting from C i is reached is independent of the history before C i is reached. Suppose that if the TPN starts running from class C i at time 0, it will reach class C i at global time interval [x, y]. Then we know that if the TPN starts running from class C i at time a, it will reach class C i at global time interval [x+a, y+a]. Futhermore, if the TPN starts running from class C i at time interval ST i= [a, b], it will reach class C i at global time interval ST i = [min{x+a, x+b}, max{y+a, y+b}] = [x+a, y+b]. Because the time span that the TPN runs from C i to C j is independent of the starting time, so it follows from Theorem 1 that the time span is [x, y], or ST j −ST i. t Corollary 1 is very useful for timeliness analysis. As mentioned in [12], the key issue of timeliness analysis is to verify whether a marking can be reached with timing constraints. Corollary 1 shows that theconcept of GSC classes helps establish quantitative timing relationship between any two reachable classes in a firing schedule.C. Reachability Analysis through State Class GraphsThe major purpose of generalized state classes is meant for the timeliness analysis of firing schedules. General reachability analysis is conducted in two separate steps. 1) Generating state class graph without considering the time stamps and global firing domains. Two state classes are viewed as identical if and only if they have the same firable transitions and corresponding relative firing intervals. This is similar to the traditional state class graph, except the timing inequalities on transition pairs. Since there are no timing inequalities on transition pairs, the functional reachability analysis is generally more efficient. 2) If a goal marking is reached in the state class graph, analyzing the time delay of the schedule that reaches the goal. An example illustrating this will be given in next section.IV. A N E XAMPLETo illustrate our approach, this section describes the modeling and analysis of a simple yet typical manufacturing system, which is composed of 5 machines and 1 assembler, as shown in Figure 2. The system receives two types of parts (A and B) as inputs. A-parts go to machine 1 for processing, whereas B-parts go to machine 2 for processing. After being processed by machine 2, B-parts go to either machine 3, or machines 4 and 5 for processing. After a pair of A-part and B-part gets processed, they are sent for assembly, where a final product is produced. Assume that the processing of machine 1 on an A-part takes 2 to 9 time units, the processing of machine 2, machine 3, machine 4, and machine 5 on a B-part takes 1 to 3, 3 to 7, 1 to 2, and 2 to 5 time units, respectively. The assembler takes 2 to 4 time units.Fig 2. A manufacturing system.The TPN model of this system is shown in Fig. 3. Table 1 describes its places and transitions.Fig 3. The TPN model for the example manufacturing systemTable 1. Legends of the TPN in Fig. 3.Place Descriptionp1 A-part bufferp2 B-part bufferp3 A-part ready for assemblyp4 B-part processed by machine 2p5 B-part being processed by machine 5p6 B-part ready for assemblyp7 Buffer for final productsTransition Description Time intervalt1 Machine 1 works on A-part [2, 9]t2 Machine 2 works on B-part [1, 3]t3 Machine 3 works on B-part [3, 7]t4 Machine 4 works on B-part [1, 2]t5 Machine 5 works on B-part [2, 5]t6 Assembler works on a pair of A- and B- parts [2, 4]Let us first analyze the timeliness of schedule t2t4t5t1t6. The initial GSC class is C0 = (M0, D0, AD0, ST0) whereST0= [0, 0].M0= (1 1 0 0 0 0 0)T,D0= {D0(t1): [2, 9] , D0(t2): [1, 3]}.AD0= {AD0(t1): [2, 9] , AD0(t2): [1, 3] }.Thus,MLFT(C0) = min{ LFT0(t1), LFT0(t2) } = {9, 3} = 3.MALFT(C0) = min{ ALFT0(t1), ALFT0(t2) } = {9, 3} =3Both t1 and t2 are firable. Firing t2 will reach GSC class C1 = (M1, D1, AD1, ST1). Following Step 1 in section III-A, the dynamic relative firing interval for t2 is [1,3], and ST1 = [AEFT0(t1), MALFT(C0)] = [1, 3]. Following Step 2, we have:M′1 = M0−B(t1)= (1 0 0 0 0 0 0)T.D1(t1) = [0, 8].AD1(t1) = [2, 9].By Step 3, M1 = M′1 + F(t1)= (1 0 0 1 0 0 0) T, under which there are two newly enabled transitions t3 and t4.D1(t3) = [3, 7].D1(t4) = [1, 2].AD1(t3) = [3, 7]+ ST1= [4,10].AD1(t4) = [1, 2]+ST1 = [2, 5].Under GSC class C1, t1 and t4 are firable. But t3 is not firable because EFT1(t3)=3 > min{LFT1(t1), LFT1(t3), LFT1(t4)} = 2. Note that, AEFT1(t3)=4 < min{ALFT1(t1), ALFT1(t3), ALFT1(t4)} = 5 . The global firing intervals cannot be used to determine the fireability of t3 (in the clock-stamped state class method, t3 would be firable). If t4 fires, its relative firing interval is [1, 2]. Similarly, we can get a new GSC class, say C2, where:M2 = (1 0 0 0 1 0 0)T.ST2 = [2, 5].D2(t1) = [0, 7].AD2(t1) = [2, 9].D2(t5) = [2, 5].AD2(t5) = [2, 5]+ST2 = [4, 10].Under C2, both t1 and t5 are firable. The relative firing interval of t5 is [2, 5]. Firing t5 reaches GSC class C3 such that:M3 = (1 0 0 0 0 1 0)T.ST3 = [AEFT2(t5), min{ALFT2(t1), ALFT2(t5)}] = [4, 9]D3(t1) = [0, 5].AD3(t1) = [max{ELFT2(t1), ELFT2(t5)}, ALFT2(t1)] = [4, 9].Under C3, only t1 is enabled and firable. Firing t1 leads to GSC class C4, where:。

Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages

Inaugural DissertationzurErlangung der Doktorw¨u rdeder Naturwissenschaftlich-Mathematischen Gesamtfakult¨a tderRuprecht-Karls-Universit¨a tHeidelbergvorgelegt vonDiplom-Mathematiker Bernd Borchertaus L¨u nne im Emsland1994F¨u r meine ElternPredicate Classes,Promise Classes,and theAcceptance Power of Regular Languages Gutachter:Prof.Dr.Klaus Ambos-Spies,Universit¨a t Heidelberg Prof.Dr.Klaus W.Wagner,Universit¨a t W¨u rzburg Tag der m¨u ndlichen Pr¨u fung:20.Dezember1994PrefaceTheoretical Computer Science This Ph.D.thesis was written in the time from January 1991until July 1994and is submitted to the Department of Mathematics of the University of Heidelberg.It contributes some results to Structural Complexity Theory which is a subﬁeld of Theoretical Computer Science.First of all I have to thank my advisor Prof.Klaus Ambos-Spies for his con-tinuing guidance and support.He also gave several crucial hints for the results of this thesis.Also I have to thank Prof.Juris Hartmanis and his former students Richard Chang,Suresh Chari,Desh Ranjan,and Pankaj Rohatgi.The initial results leading to this thesis were observed while I was visiting Cornell University in spring 1992.This is the right place to express gratitude to Prof.Steven Homer and Prof.Ak-ihiro Kanamori from Boston University who six years ago led me to the interest-ing ﬁeld of Structural Complexity Theory.Also I would like to thank Prof.Klaus Weihrauch,University of Hagen,for supervising my ﬁrst diploma thesis,and Prof.Wolfgang Sch¨o nfeld,IBM Heidelberg,for his guidance while I was working in his group.For helpful discussions I would like to thank Andreas Eisenbl¨a tter,Ulrich Her-trampf,Birgit Jenner,Klaus-J¨o rn Lange,Pierre McKenzie,Wolfgang Merkle,An-dre Nies,Thomas Schwentick,Nikolai Vereshchagin,and Heribert Vollmer.I am grateful to Prof.Klaus W.Wagner,University of W¨u rzburg,who agreed to referee this thesis.The results of Part I of the thesis were presented at the 9th Annual IEEE Con-ference of Structure in Complexity Theory 1994,see [Bo94b],a journal version will be submitted.The results of Part II were presented at the 11th Annual Sym-posium of Theoretical Aspects of Computer Science (STACS)1994,see [Bo94a],a journal version will appear in .Heidelberg,July 1994iiiContents1Introduction11.1Outline of Part I11.2Ouline of Part II21.3Related Work2I Predicate Classes and Promise Classes52Preliminaries52.1Order-Theoretic Notions52.2Recursively Presentable Classes62.3Polynomial Time Many-One Reducibility72.4Polynomial Time Many-One Degrees72.5Principal Ideals82.6Ideals112.7Computation Trees153Predicate Classes173.1The Deﬁnition of Predicate Classes173.2The Characterization of Predicate Classes194Promise Classes224.1The Deﬁnition of Promise Classes224.2The Characterization of the Promise Classes244.3Consequences of the Characterization of the Promise Classes295Analogous Results for Other Nondeterministic Computation Models305.1Balanced Polynomial Time Turing Machines305.2Polynomial Time Bit-Reducibility315.3Polynomial Time Nondeterministic Transducers335.4Polynomial Time Function Classes345.5Relativized Predicate Classes35iiiII On the Acceptance Power of Regular Languages396Predicate Classes Accepted by Regular Languages396.1Predicate Classes Accepted by Languages396.2The Deﬁnition of Regular Languages406.3Predicate Classes Accepted by Regular Languages417A Lemma about Regular Languages437.1o-h-Reducibility437.2Generalized Deﬁnite Languages467.3The Main Lemma468A Result for Classes Accepted by Regular Languages488.1The Main Result488.2A Non-Density Result on the Assumption that PH does not Collapse508.3A Non-Density Result for the Relativized Case518.4An Analogous Result for the Log-Space Case53 References55 Subject Index63 Symbol Index64 Index of Classes65iv1Introduction1.1Outline of Part Ipolynomial time many-one reducibility polynomial time nondeterministic computation regular language accepted predicate classes principal ideal promise function Part I of this thesis observes a close connection between two basic concepts of Structural Complexity Theory,both introduced by Karp in [Ka72]:1.The concept of which since its deﬁ-nition was studied intensively,see for example [La75,AS85a].2.The concept of ,in the slightly more general sence as it is used to deﬁne not only the class NP (like in the original paper)but also classes like P,PP,UP,BPP,and RP.Part II of this thesis relates the concepts of Part I to the notion of a .More detailed outlines of the two parts and references to related work are given below.Several complexity classes –like NP,P,and PP –are deﬁned (say )by a predicate on computation trees produced by polynomial time nondeterministic Turing machine computations.Such classes will be called .For example NP is accepted by the predicate on computation trees which is 1if and only if the tree contains a leaf with label 1.As another example,P is accepted by the predicate on computation trees which is 1if and only if the tree contains an odd number of leaves with label 1.Call a class a if with re-spect to polynomial time many-one reducibility it has a complete set and is closed downward.It is well known that the example classes NP,P,and PP are principal ideals.This observation can be generalized:The set of predicate classes is equal to the set of principal ideals.After the preliminary deﬁnitions and observations in Chapter 2this theorem will be shown in Chapter 3.In Chapter 4complexity classes like UP,BPP,and RP will be considered.These classes have in common that their original deﬁnition can be seen the fol-lowing way:there is a 01-valued function –called –on1.2Ouline of Part II1.3Related Workpromise classes accepted ideal yield computation trees where it is presumed (=’promised’)for each machine accept-ing a language in the class that for each input the promise function is not for the corresponding computation tree.Such classes will be called .For example UP is deﬁned (say )by the promise function on computation trees which has the value 0if the tree does not contain a leaf with label 1,which has the value 1if the tree contains exactly one leaf with label 1,and which has the value if the tree contains more than one leaf with label 1.Call a class an if with respect to polynomial time many-one reducibility it is closed downward and closed under join.It is easy to see that the example classes UP,BPP,and RP are countable ideals.Like before,this observation can be generalized:The set of promise classes is equal to the set of countable ideals.The two characterizations of predicate classes and promise classes described above –and their corresponding versions for the recursive case –are the two main results of Part I of this thesis.In Chapter 5analogous results for some other models of nondeterministic computation will be shown.In Part II predicates with a low complexity will be considered:the predicates which are determined by a regular language for the the yields of computation trees (the is the left-to-right concatenation of the leaf labels).For example,NP is accepted by the predicate determined by the regular language which consists of the words containing at least one letter 1.The main result of Part II will be that if the class determined by a (nontrivial)regular language is not equal to P then the class contains at least one of the classes NP,co-NP and MOD P for prime.This will be interpreted as a non-density result in two ways:(1)on the as-sumption that the Polynomial Time Hierarchy does not collapse,and (2)for the relativized case.Additionally,the analog of the main result for the log-space case is shown.Similar work like in Part I was done in Bovet,Crescenzi,and Silvestri in [BCS91,BCS92],by Vereshchagin in [Ve93],by Hertrampf,Lautemann,Schwentick,Voll-locally deﬁnable acceptance types mod-classes ﬁnite acceptance types mer,and Wagner in [HL*93],and by Jenner,McKenzie,and Th´e rien in [JMT94].Like in Part I of this thesis also in these papers the deﬁnability of complexity classes with the help of nondeterministic computation models is investigated.The classes determined by regular languages,see Part II,were ﬁrst considered by Hertrampf,Lautemann,Schwentick,Vollmer,and Wagner in [HL*93].These classes are a special case (namely the associative case)of the classes determined by deﬁned by Hertrampf in [Her92a,Her94b].On the other hand the and the classes determined by ,considered systematicly in [Her90,Bei91,BG92]and [GW87,Her94a],re-spectively,are classes which are by deﬁnition determined by regular languages.Part I2Preliminaries2.1Order-Theoretic NotionsPredicate Classes and Promise Classesrecursively presentable classes polynomial time many-one reducibility degrees,principal ideals ideals computation trees binary relation reﬂexive transitive symmetric antisymmetric preorder partial order equivalence relation isomorphic -complete -minimum -maximum -supremum -inﬁmum supremum First some standard order-theoretic notions will be deﬁned in Section 2.1.The well-known concept of will be deﬁned in Section2.2.Then the and its notions of and are presented in the Sections 2.3–2.6.Section 2.7introduces .The following order-theoretic notions are standard,see for example [Gr78].A on a set is a subset of .Only the inﬁx notation will be used,i.e.stands for ().A binary relation is if for all ,it is if from and it follows ,it is if from it follows ,and it is if from and it follows =.A is a reﬂexive and transitive binary relation on a nonempty set.A is a preorder which is antisymmetric,and an is a preorder which is symmetric.A binary relation on a set and a binary relation on a set are called if there exists an isomorphism,i.e.a bijective mapping from to such that ()().Let be a preorder on a set .An element is called for a subset if and holds for all .A ()is an elementsuch that ()for all .For two elements a ()of and is an element such that and (and )and if also for another element it holds that and (and )then ().If it is clear from the context that one is dealing with a preorder ,a –supremum will just be called ,this will be done the same way for other order-theoretic notions.ΣΣ()()2.2Recursively Presentable ClassesPredicate Classes and Promise Classesupper semi-lattice lattice distributive -chain -antichain -atom atomic dense language words class recursively presentable recursive language 6Part I Let be a partial order on a set .Note that for a partial order the supremum (inﬁmum)of two elements,if it exists,is unique.The partial order is called an if the supremum exists for every pair of elements,it is called a if both supremum and inﬁmum exist for every pair of elements.A binary relation on a set is called an (upper semi-)sublattice of an (upper semi-)lattice on a set if is a subset of ,is the restriction of to ,and is closed under -suprema (and -inﬁma).Note that an (upper semi-)sublattice is an (upper semi-)lattice.An (upper semi-)lattice is called if for all elements the following holds:if ,where is the supremum of and ,then there are elements such that ,,and is the supremum of and .Let be a partial order on a set .Two elements are called -comparable if or .A subset is called a if any two elements of are comparable,is called an if any two elements are incomparable.If the minimum exists then an element =is called anif no element =exists such that .The partial order is called if for every element =there is an atom such that .A partial order is called if for any two comparable but different elements there is an element properly between them,formally:for all for which but notthere is a such that and but neither nor .A partial order which contains an atom is obviously not dense because there is no element properly between the minimum and the atom.In this thesis a will always be a set of words over the alphabet =01,for basic deﬁnitions like the one of see for example [HU79].A is a set of languages.Let be the (+1)st word of in the length-lexicographic order,see for example [AS89].For a language and an I N deﬁne to be the languagewhere is a usual bijective polynomial time computable pairingfunction,see for example [BDG88].Call,like in [BDG88,AS89],a complexityclass if =I N for some recursive ,forthe notion of a see for example [HU79].ΣΣΣΣΣPreliminaries 2.3Polynomial Time Many-One Reducibility2.4Polynomial Time Many-One Degreesjoin polynomial time many-one equivalent polynomial time many-one degree of a language trivial recursive 7Let FP denote the class of functions which can be computed by a Tur-ing machine running in deterministic polynomial time,see for example [HU79,BDG88]for a more detailed deﬁnition.Let denote the polynomial time many-one reducibility among languages,i.e.if there exists a function FP such that ()for all words .The original deﬁnition of this reducibility is from Karp in [Ka72].It is easy to see that the binary relation is a preorder on the set of all languages.Deﬁne the of two languagesto be the language 01.The join is a -supremum of and :and for all languages :.The following enumeration of FP will be useful.Let in some straightforward way the deterministic Turing machines which compute functions be encoded by words.Deﬁne for every the function FP to be the function computed by the following polynomial time deterministic Turing machine:on input the machine simulates the computation of the deterministic Turing machine encoded by and cancels the simulation –with output –if the simulated machine has not terminated after +steps.It is easy to see that FP =I N and that the function which maps to ()is recursive.For the notions of this section see for example [La75,AS85a].Two languagesare called ,in short ,ifand .Note that is an equivalence relation on the set of all languages.Let the ,in short deg (),be the set of languages polynomial time many-one equivalent to ,and let denote the partial order on the -degrees deﬁned bydeg ()deg ():Note that this deﬁnition does not depend on the choice of and .The degree deg ()is the unique -supremum of deg ()and deg ().This shows that is an upper semi-lattice on the set of all polyno-mial time many-one degrees.The two degrees and are called the degrees.Call a degree deg ()if and therefore all languages in deg ()are recursive.ΣΣΣΣ2.5Principal IdealsPredicate Classes and Promise ClassesTheorem 2.1(Ladner 1975,Ambos-Spies 1985a)The following partial orders are distributive upper semi-lattices,the one in (b)is an upper semi-sublattice of the one in (a).(a)The partial order on the set of all nontrivial polynomial time many-one degrees.(b)The partial order on the set of the nontrivial recursive polynomial time many-one degrees.This upper semi-lattice is additionally dense.principal-ideal principal ideal lower cone of downward closure of principal ideal trivial8Part I Many results are known for the partial order .In this thesis only the following basic results about density and distributivity due to Ladner in [La75]and Ambos-Spies in [AS85a],respectively,will be considered.Call a set of languages a ,or simply ,if there exists a language such that =():=.There areseveral other names for the class (),sometimes it is called or .For the choice of the name see the next section.Note that the language is -complete for ().The following classes are examples of principal ideals.The class NP should be mentioned ﬁrst as an example of a principal plete languages for NP,like the problem SAT,were –for polynomial time Turing reducibility –ﬁrst presented by Cook in [Co71],their -completeness was shown in [Ka72,Le73].For a list of -complete prob-lems for NP see [GJ79].The fact that for example SAT is not only -complete for NP but also every language -reducible to SAT is in NP is easy to see.The two principal ideals=(),=()will be called principal ideals.The class P is a principal ideal ()where is any language in P.P contains the two trivial principal ideals and is contained in every nontrivial principal ideal,see Figure 1.=2ΣΣΠ∆Preliminaries 9PFigure 1:The two trivial principal ideals and PNot only P and NP but also all other classes and of the Polyno-mial Time Hierarchy are principal ideals,the existence of -complete lan-guages was shown in [St77,Wr77].Let be any language.Then the class P consisting of all languages com-putable in polynomial time with oracle (see for example [Co71,BDG88]and also Section 5.5)is a principal (many-one)ideal according to the results in [AS86a],see also Corollary 5.8.As a special case,the classes of the Polynomial Time Hierarchy are principal ideals.The classes NP(n)and co-NP(n)of the Boolean Hierarchy are principal ide-als,the existence of -complete languages was shown in [CG*88].Counting classes like PP,C P,MOD P,P =MOD P,US =1–NP are principal ideals,for the original deﬁnitions see [Gi77,Wa86b,BG92,PZ83,BGu82,GW87].The exponential time classes EXPTIME =DTIME(2poly )and NEXPTIME =NTIME(2poly )are principal ideals.More generally,the classes -EXPTIME=DTIME(2...2poly )and -NEXPTIME =NTIME(2...2poly ),where inboth cases the exponentiation tower has height ,can easily be shown to be principal ideals for every 1.For the exact deﬁnitions see for example [Jo90].()()()Predicate Classes and Promise Classes Proposition 2.1Proof.Corollary 2.1Proposition 2.2Proof.For all languages it holds:()()For all languages it holds:()()Let be a language.()is recursively presentable is recursiveis recursive.10Part I There is a strong connection between the inclusion order on the principal ideals and the partial order on the polynomial time many-one degrees.deg ()deg ()Note that the second equivalence holds by the deﬁnition of.In order to see the ﬁrst equivalence assume that ()().Because()it holds by the assumption that (),this shows .If on the other side then for each it holds by the transitivity of that ,this shows ()()In other words,the inclusion order on the principal ideals is isomorphic to the -order on the polynomial time many-one degrees.It is clear by the proof that this isomorphism between the partial order on the degrees and the inclusion order on the principal ideals exists not only for but for every preorder.The following corollary follows immediately from Proposition 2.1.=deg ()=deg ()By the following proposition the property of being recursively presentable is determined for a principal ideal by any -complete language.deg ()Note that the second equivalence was already mentioned in the deﬁnition of the recursiveness of a -degree.In order to see the ﬁrst equivalence assume that ()=I N forsome recursive language .Then =for some I N.But if is recursivethen also =is.For the other direction let a recursive language be given.Deﬁne the language :=(),the functions were deﬁned in Section 2.3.It is easy to see that is recursive and that ()==I N :()2.6IdealsPreliminariesCorollary 2.2Proposition 2.3Proof.The following partial orders are distributive upper semi-lattices.The one in (b)is an upper semi-sublattice of the one in (a).(a)The inclusion order on the set of all nontrivial principal ideals.(b)The inclusion order on the set of all nontrivial recursively presentable principal ideals.This upper semi-lattice is additionally dense.-ideal ideal ideal (a)The principal ideals are exactly the ideals which have a-complete language.(b)The recursively presentable principal ideals are exactly the ideals which have a recursive -complete language.11:()=I N .This ﬁnishes the proof of the fact that the class ()is recursively presentable if and only if is recursive.By Propositions 2.1and 2.2the results for the polynomial time many-one de-grees stated in Theorem 2.1can be transfered to the principal ideals immediately.A ,or simply ,is a nonempty set of languages such that if lan-guages and are in then each language with is also in .In other words,an ideal is a nonempty set of languages which is closed under join und closed downward.The name follows the notation in Lattice Theory,see for example Gr¨a tzer [Gr78].The following proposition shows the relation between between ideals and prin-cipal ideals.(a)Let a principal ideal()be given.is -complete for ()because is in ()and by deﬁnition all languages in ()are -reducible to .It remains to show that ()is an ideal.Let ()and.Then by the supremum property of the join.By the transitivity of it follows that ().Therefore,()is an ideal.For the other direction let an ideal have a -complete language .It will be shown that =().It holds ()because every language in is -reducible to .And it holds ()because and I is closed downward.ΣΣΠΣI N I N 1trivial ideals Predicate Classes and Promise Classes12Part I Part (b)follows from part (a)and Proposition 2.2.The two trivial principal ideals and will be also be called .Like in the case of principal ideals it is easy to see that the ideal P contains the two trivial ideals and every nontrivial ideal contains P.Some examples of classes are given which are ideals but which are not princi-pal ideals or not known to be principal ideals.Classes like UP (deﬁned in [Va76]),BPP,RP (both deﬁned in [Gi77]),FewP (deﬁned as FNP in [Al86]),and AM (deﬁned in [Ba85]),are easily shown to be (recursively presentable)ideals.These classes are not known to be principal ideals,see [Si82,Kow84,AS86b,HH88,Hem88,AS89].In Proposition 2.5it will be shown that pairwise intersections of nontrivial (recursively presentable)ideals are nontrivial (recursively presentable)ide-als,like (for1)or ZPP =RP co-RP.Generally,it is not known if such an intersection is a principal ideal.For a discussion of this question for the class NP co-NP see [Si82,Kow84,HI85,Hem88,AS89].(Effective)inﬁnite unions of increasing sequences of (recursively presentable)ideals,like the class of languages of the Polynomial Time Hierarchy PH=and the class of languages of the Boolean Hierarchy BH=NP(n),are (recursively presentable)ideals which are in general not known to be principal ideals.For the original deﬁnitions of PH and BH see [St77,Wr77,CG*88].Let the class ELEMENT ARY be the union -EXPTIME,for the deﬁni-tion of the classes -EXPTIME for 1see the examples of principal ide-als in Section 2.5.The class ELEMENTARY is a (recursively presentable)ideal which is provably not a principal ideal because by the Time Hierarchy Theorem of [HS65]it can be shown for each 1that -EXPTIME is a proper subset of (+1)-EXPTIME.The class of all recursive languages is a countable ideal but neither a prin-cipal ideal nor a recursively presentable ideal.The class P/poly deﬁned by Karp and Lipton in [KL80,KL82]can easily be shown to be an ideal.It is not countable,but for example P/poly NP is a countable ideal.PreliminariesProposition 2.4Proof.Proposition 2.5(a)Every recursively presentable ideal is a countable ideal.(b)Every principal ideal is a countable ideal.(c)There is a recursively presentable ideal which is not a principal ideal.(d)There is a principal ideal which is not recursively presentable.(e)There is an ideal which is not countable.The following partial orders are distributive lattices,the one in (b)is a sublattice of the one in (a),and the one in (c)is a sublattice of the ones in (a)and (b).(a)The inclusion order on the set of all nontrivial ideals.(b)The inclusion order on the set of all nontrivial countable ideals.(c)The inclusion order on the set of all nontrivial recursively presentable ideals.In (a),(b)and (c)the inﬁmum of two nontrivial ideals and is given by their intersection,and the supremum is given by the smallest ideal containing both and .13The class of all languages is an ideal but not countable.The following classes are not ideals.The class E =DTIME(2lin )is recursively presentable,has a -complete language,and is closed under join but is not an ideal because it is not closed downward.A polynomial time many-one degree is an ideal if and only if it is one of the two trivial degrees because otherwise it is not closed downward.For two -incomparable recursive languages the class ()()is recursively presentable and closed downward but is not an ideal because it is not closed under join.The relation of the different types of ideals introduced so far is described by the following Proposition 2.4,see also Figure 2.(a)Every recursively presentable class is by deﬁnition countable.(b)A principal ideal ()is by Proposition 2.3an ideal,and it is countable because there are at most countably many -reductions.A witness for (c)is the class ELEMENTARY,see the examples above,and a witness for (d)is according to Propositions 2.2and 2.3any class ()for a non-recursive .A witness for (e)is the class P/poly,see the examples above.()()Proof.Predicate Classes and Promise Classes14Part I recursively presentable principal idealsrecursively presentable ideals principal idealscountable idealsidealsFigure 2:Types of Ideals(a)Let two nontrivial ideals and be given.It will be shown thatis a nontrivial ideal.Therefore,is the inﬁmum of and .Because both and contain the class P also the class contains P and is not empty.Letfor two languages ,then both and containand .Therefore,they contain also by their property of being an ideal.This shows that is a nontrivial ideal.The supremum of and is the class =:.It is easy to see that this class is an ideal,that it contains both and ,and that it is contained in every ideal containing both and .For the distributivity let be as above and let be contained in .Now it is shown that the supremum of =and =equals .and and therefore also their supremum are contained in .For the other direction it obviously sufﬁces to show that for every language in the principal ideal ()is the supremum of two principal ideals in and ,respectively.By deﬁnition of there exist sets such that ,in other words ()is contained in the supremum of ()and ().By the distributivity of the principal ideals there are languages ()()such that ()is the supremum of ()and ().(b)By the property of a sublattice to be a lattice it sufﬁces to observe that for two given countable nontrivial ideals and the classes and from (a)are countable.The distributivity follows like in (a).(c)It sufﬁces like in (b)to show that for two recursively presentable ideals=I N and =I N (for recursive languages and )Preliminaries ()()()()()()()()()2.7Computation TreesTheorem 2.2(Ambos-Spies 1986)Theorem 2.3(Shinoda &Slaman 1990)Proposition 2.6exact pair theorems For a recursively presentable ideal thereexist two recursive languages and such that ()().For a countable ideal there exist two languages and such that ()().(a)The nontrivial countable ideals are exactly the pairwise in-tersections of the nontrivial principal ideals.(b)The nontrivial recursively pre-sentable ideals are exactly the pairwise intersections of the nontrivial recursively presentable principal ideals.15the classes and from (a)are also recursively presentable.Deﬁne tobe the recursive language and for all with itholds that .It will be shown that this constructionguarantees that =I N .The inclusion from left to right is obvious.For the other direction consider a ﬁxed :if is inﬁnite,then it is also an (inﬁnite)language of both and ,and if is ﬁnite then it is in P and thereforein .This shows =I N .To represent the class deﬁne tobe the language (),where was deﬁnedin Section 2.3.It is easy to check that is recursive,and by construction it holdsthat =I N .The distributivity follows like in (a).The following two results –called –of Ambos-Spies in[AS86b]and Shinoda and Slaman in [ShS90]relate the notions of ideals and prin-cipal ideals more closely.The latter was shown to hold for the polynomial time Turing reducibility but the proof is also valid for the many-one case.==For the nontrivial ideals the two Theorems 2.2and 2.3can by Proposition 2.5be expressed the following way.Consider nondeterministic Turing machines as presented for example in [BDG88].In this thesis it is additionally assumed for a Turing machine that for a state and a tupel of symbols read by the heads at most two transitions are speciﬁed by the transition function,and also it is assumed that the transition function is given as a linear list.This way it is guaranteed that if nondeterminism appears during a。

Generalised chiral QED2 Anomaly and Exotic Statistics

a r X i v :h e p -t h /9705178v 1 23 M a y 1997Generalized Chiral QED 2:Anomaly and Exotic StatisticsFuad M.SaradzhevInstitute of Physics,Academy of Sciences of Azerbaijan,Huseyn Javid pr.33,370143Baku,AZERBAIJANABSTRACTWe study the inﬂuence of the anomaly on the physical quantum picture of the generalized chiral Schwinger model deﬁned on S 1.We show that the anomaly i)results in the background linearly rising electric ﬁeld and ii)makes the spectrum of the physical Hamiltonian nonrelativistic without a massive boson.The physical matter ﬁelds acquire exotic statistics.We construct explicitly the algebra of the Poincare generators and show that it diﬀers from the Poincare one.We exhibit the role of the vacuum Berry phase in the failure of the Poincare algebra to close.We prove that,in spite of the background electric ﬁeld,such phenomenon as the total screening of external charges characteristic for the standard Schwinger model takes place in the generalized chiral Schwinger model,too.PACS numbers:03.70+k ,11.10.Mn.1IntroductionThe two-dimensional QED with massless fermions,i.e.the Schwinger model(SM),demonstrates such phenomena as the dynamical mass generation and the total screening of the charge[1].Although the Lagrangian of the SM contains only masslessﬁelds,a massive bosonﬁeld emerges out of the interplay of the dynamics that govern the originalﬁelds.This mass generation is due to the complete compensation of any external charge inserted into the vacuum.In the chiral Schwinger model(CSM)[2,3]the right and left chiral components of the fermionic ﬁeld have diﬀerent charges.The left-right asymmetric matter content leads to an anomaly.At the quantum level,the local gauge symmetry is not realized by a unitary action of the gauge symmetry group on Hilbert space.The Hilbert space furnishes a projective representation of the symmetry group[4,5,6].In this paper,we aim to study the inﬂuence of the anomaly on the physical quantum picture of the CSM.Do the dynamical mass generation and the total screening of charges take place also in the CSM?Are there any new physical eﬀects caused just by the left-right asymmetry?These are the questions which we want to answer.To get the physical quantum picture of the CSM we needﬁrst to construct a self-consistent quantum theory of the model and then solve all the quantum constraints.In the quantization procedure,the anomaly manifests itself through a special Schwinger term in the commutator algebra of the Gauss law generators.This term changes the nature of the Gauss law constraint:instead of beingﬁrst-class constraint,it turns into second-class one.As a consequence,the physical quantum states cannot be deﬁned as annihilated by the Gauss law generator.There are diﬀerent approaches to overcome this problem and to consistently quantize the CSM. The fact that the second class constraint appears only after quantization means that the number of degrees of freedom of the quantum theory is larger than that of the classical theory.To keep the Gauss law constraintﬁrst-class,Faddeev and Shatashvili proposed adding an auxiliaryﬁeld in such a way that the dynamical content of the model does not change[7].At the same time,after quantization it is the auxiliaryﬁeld that furnishes the additional”irrelevant”quantum degrees of freedom.The auxiliaryﬁeld is described by the Wess-Zumino term.When this term is added to the Lagrangian of the original model,a new,anomaly-free model is obtained.Subsequent canonical quantization of the new model is achieved by the Dirac procedure.For the CSM,the correspondig WZ-term is not deﬁned uniquely.It contains the so called Jackiw-Rajaraman parameter a>1.This parameter reﬂects an ambiguity in the bosonization procedure and in the construction of the WZ-term.The spectrum of the new,anomaly-free model turns out to be relativistic and contains a relativistic boson.However,the mass of the boson also depends on the Jackiw-Rajaraman parameter[2,3].This mass corresponds therefore to the”irrelevant”quantum degrees of freedom.The quantum theory with such a parameter in the spectrum is not physical,i.e. thatﬁnal version of the quantum theory which we would like to get.The latter should not contain any nonphysical parameters,otherwise one can not say anything about a physical quantum picture.In another approach also formulated by Faddeev[8],the auxiliaryﬁeld is not added,so the quantum Gauss law constraint remains second-class.The standard Gauss law is assumed to be regained as a statement valid in matrix elements between some states of the total Hilbert space,and it is the states that are called physical.The theory is regularized in such a way that the quantum Hamiltonian commutes with the nonmodiﬁed,i.e.second-class quantum Gauss law constraint.The spectrum turns out to be non-relativistic[9,10].Here,we follow the approach given in our previous work[11].The pecularity of the CSM is that its anomalous behaviour is trivial in the sense that the second class constraint which appears afterquantization can be turned intoﬁrst class by a simple redeﬁnition of the canonical variables.This allows us to formulate a modiﬁed Gauss law to constrain physical states.The physical states are gauge-invariant up to a phase,the phase being1-cocycle of the gauge symmetry group algebra.In [12,13,14],the modiﬁcation of the Gauss law constraint is obtained by making use of the adiabatic approach.Contrary to[11]where the CSM is deﬁned on R1,we suppose here that space is a circle of lengthL,−L2,so space-time manifold is a cylinder S1×R1.The gaugeﬁeld then acquires aglobal physical degree of freedom represented by the non-integrable phase of the Wilson integral on S1.We show that this brings in the physical quantum picture new features of principle.Another way of making two-dimensional gaugeﬁeld dynamics nontrivial is byﬁxing the spatial asymptotics of the gaugeﬁeld[15,16].If we assume that the gaugeﬁeld deﬁned on R1diminishes rather rapidly at spatial inﬁnities,then it again acquires a global physical degree of freedom.We will see that the physical quantum picture for the model deﬁned on S1is equivalent to that obtained in[15,16].We consider the general version of the CSM with a U(1)gaugeﬁeld coupled with diﬀerent charges to both chiral components of a fermionicﬁeld.We show that the charges are not arbitrary,but satisfy a quantization condition.The SM where these charges are equal is a special case of the generalized CSM.This will allow us at each step of our consideration to see the distinction between the two models.We work in the temporal gauge A0=0in the framework of the canonical quantization scheme and the Dirac’s quantization method for the constrained systems[17].We use the system of units where c=1.In Section2,we quantize our model in two steps.First,the matterﬁelds are quantized, while A1is handled as a classical backgroundﬁeld.The gaugeﬁeld A1is quantized afterwords,using the functional Schrodinger representation.We derive the anomalous commutators with nonvanishing Schwinger terms which indicate that our model is anomalous.In Section3,we show that the Schwinger term in the commutator of the Gauss law generators is removed by a redeﬁnition of these generators and formulate the modiﬁed quantum Gauss law constraint.We prove that this constraint can be also obtained by using the adiabatic approximation and the notion of quantum holonomy.In Section4,we construct the physical quantum Hamiltonian consistent with the modiﬁed quan-tum Gauss law constraint,i.e.invariant under the modiﬁed gauge transformations both topologically trivial and non-trivial.We introduce the modiﬁed topologically non-trivial gauge transformation op-erator and deﬁneθ–states which are its eigenstates.We consider in detail the case of the SM and demonstrate its equivalence to the freeﬁeld theory of a massive scalarﬁeld.For the generalized CSM,we deﬁne the exotic statistics matterﬁeld and reformulate the quantum theory in terms of thisﬁeld.In Section5,we construct two other Poincare generators,i.e.the momentum and the boost.We act in the same way as before with the Hamiltonian,namely we deﬁne the physical generators as those which are invariant under both topologically trivial and non-trivial gauge transformations.We show that the algebra of the constructed generators is not a Poincare one and that the failure of the Poincare algebra to close is connected to the nonvanishing vacuum Berry curvature.In Section6,we study the charge screening.We introduce external charges and calculate(i)the energy of the ground state of the physical Hamiltonian with the external charges and(ii)the current density induced by these charges.Section7contains our conclusions and discussion.2Quantization Procedure2.1Classical TheoryThe Lagrangian density of the generalized CSM isL=−10,1,γ0=σ1,γ1=−iσ2,γ0γ1=γ5=σ3,σi(i=2(1±γ5)ψ.In the temporal gauge A0=0,the Hamiltonian density isH=H EM+H F,(2) where H EM=12)=A1(L2)=ψ±(L¯he±λ}ψ±,generated byG=∂1E+e+j++e−j−,λbeing a gauge function,as well as under global gauge transformations of the right-handed and left-handed Diracﬁelds which are generated byQ±=e± L/2−L/2dxj±(x).Due to the gauge invariance,the Hamiltonian density is not uniquely determined.On the con-strained submanifold G≈0of the full phase space,the Hamiltonian density˜H=H+v H·G,(4) where v H is an arbitrary Lagrange multiplier which can be any function of theﬁeld variables and their momenta,reduces to the Hamiltonian density H.In this sense,our theory cannot distinguish between H and˜H,and so both Hamiltonian densities are physically equivalent to each other.For arbitrary e+,e−the gauge transformations do not respect the boundary conditions 3.The gauge transformations compatible with the boundary conditions must be either of the formλ(L2)+¯h2πe+=N,N∈Z,(6)or of the formλ(L2)+¯h2πe−=N∈Z.(7)Eqs.6or7imply the charge quantization condition for our system.Without loss of generality, we choose the condition 6.For N=1,e−=e+and we have the standard Schwinger model.For N=0,we get the model in which only the right-handed component of the Diracﬁeld is coupled to the gaugeﬁeld.From Eq.5we see that the gauge transformations under consideration are divided into topo-logical classes characterized by the integer n.Ifλ(L2),then the gauge transformation istopologically trivial and belongs to the n=0class.If n=0it is nontrivial and has winding number n.Given Eq.5,the nonintegrable phaseΓ(A)=exp{i¯he+L b(t)}.In contrast toΓ(A),the line integralb(t)=1e+Ln.By a non-trivial gauge transformation of the formg n=exp{i2πe+L].The conﬁgurations b=0and b=¯h2πe+L.2.2Quantization and AnomalyThe eigenfunctions and the eigenvalues of theﬁrst quantized fermionic Hamiltonians ared± x|n;± =±εn,± x|n;± ,wherex|n;± =1L exp{i¯hεn,±·x},εn,±=2π2π).We see that the spectrum of the eigenvalues depends on b.For e+b Le+L,the energies ofεn,+decrease by¯h2πL N.Some of energy levels change sign.However,the spectrum atthe conﬁgurations b=0and b=¯h2π2π¯h (and e−b L2π¯h]and{e±b L2π¯h],a†n|vac;A;+ =0for n≤[e+b Landb n |vac;A ;− =0for n ≤[e −b L2π¯h ].(11)Excited states are constructed by operating creation operators on the Fock vacuum.In the ζ–function regularization scheme,we deﬁne the action of the functional derivative on ﬁrst quantized fermionic kets and bras byδδA 1(x )|n ;± ·|λεm,±|−s/2,n ;±|←δδA 1(x )|m ;± m ;±|·|λεm,±|−s/2.From 8we get the action ofδδA 1(x )a n =−lim s →0m ∈Zn ;+|δδA 1(x )a †n=lims →0m ∈Zm ;+|δδA 1(x )on b n ,b †n can be written analogously.Next we deﬁne the quantum fermionic currents and fermionic parts of the second-quantized Hamiltonian asˆj s ±(x )=12L /2−L /2dx (ψ†s ±d ±ψs ±−ψs ±d ⋆±ψ†s±).Substituting 8into these expressions,we obtainˆj s ±(x )=n ∈Z1Lnx }ρs ±(n ),whereρs +(n )≡k ∈Z12[b †k ,b k +n ]−·|λεk,−|−s/2|λεk +n,−|−s/2are momentum space charge density (or current)operators,andˆH s ±(x )=n ∈Z1Lnx }H s±(n ),H s ±(n )≡H s 0,±(n )∓e ±bρs±(n ),(12)whereH s0,+(n)≡¯hπ2[a†k,a k+n]−·|λεk,+|−s/2|λεk+n,+|−s/2,H s0,−(n)≡¯hπ2[b k+n,b†k]−·|λεk,−|−s/2|λεk+n,−|−s/2. The charges corresponding to the currentsˆj s±(x)areˆQ s±=e± L/2−L/2dxˆj s±(x)=e±ρs±(0).With Eqs.10and11,we have for the vacuum expectation values:vac;A;±|ˆj±(x)|vac;A;± =−12(ξ++ξ−),whereη±≡±lim s→01λ k∈Z|λεk,±|−s+1.Taking the sums,we obtainη±=±22π¯h}−1L(({e±b L2)2−12η±,ˆQ ±=e±:ρ±(0):−L2ξ±,where double dots indicate normal ordering with respect to|vac,A ,ˆH 0,+=¯h2π2π¯h]ka†k a k|λεk,+|−s− k≤[e+b LLlims→0{k>[e−b L2π¯h]kb†k b k|λεk,−|−s}and:ρ+(0):=lims→0{ k>[e+b L2π¯h]a k a†k|λεk,+|−s},:ρ−(0):=lims→0{ k≤[e−b L2π¯h]b k b†k|λεk,−|−s}.The operators:ˆj±(x):and:ˆH±:are well deﬁned when acting onﬁnitely excited states which have only aﬁnite number of excitations relative to the Fock vacuum.To construct the quantum electromagnetic Hamiltonian,we quantize the gaugeﬁeld using the functional Schrodinger representation.In this representation,when the vacuum and excited fermionic Fock states are functionals of A1,the gaugeﬁeld operators are represented asˆA1(x)→A1(x),ˆE(x)→−i¯hδL pxαp.Since A1(x)is a real function,αp satisﬁesαp=α⋆−p.The Fourier expansion for the canonical momentum conjugate to A1(x)is thenˆE(x)=1L¯h p∈Z p=0e−i2πdαp, whereˆπb≡−i¯h dL exp{i2πL ¯h2ddb−1dα−p+qd2Lˆπ2b−1dαqd2(ξ++ξ−).If we multiply two operators that areﬁnite linear combinations of the fermionic creation and annihilation operators,theζ–function regulated operator product agrees with the naive product. However,if the operators involve inﬁnite summations their naive product is not generally well deﬁned. We then deﬁne the operator product by mutiplying the regulated operators with s large and positive and analytically continue the result to s=0.In this way we obtain the following relations[ρ±(m),ρ±(n)]−=±mδm,−n,(15) [H0,±(n),H0,±(m)]−=±¯h2π[ˆH0,±,ρ±(m)]−=∓¯h2πdbρ±(m)=0,d2π¯hδp,±m,d2π¯hδp,±m,(p>0).(16) The quantum Gauss operator isˆG=ˆG0+2πLpx−ˆG−(p)e−i2πLe+ρN(0),ˆG ±(p)≡¯h pd2πρN(±p)andρN=ρ++Nρ−is momentum space total charge density operator.Using15and16,we easily get thatρ+(±p)(andρ−(±p))are gauge invariant.For example, forρ+(±p)we have:[ˆG+(p),ρ+(±q)]−=0,[ˆG−(p),ρ+(±q)]−=0,(p>0,q>0).The operatorsˆG±(p)don’t commute with themselves,[ˆG+(p),ˆG−(q)]−=(1−N2)e2+L24π2d3Quantum Constraints3.1Quantum SymmetryIn non-anomalous gauge theories,Gauss law is considered to be valid for physical states only.This identiﬁes physical states as those which are gauge-invariant.The problem with the anomalous be-haviour of the generalized CSM,in terms of states in Hilbert space,is apparent:owing to theSchwinger terms we cannot require that states be annihilated by the Gauss law generators ˆG±(p ).Let us represent the action of the topologically trivial gauge transformations by the operatorsU 0(τ)=exp {i¯hp>0(ˆG+τ++ˆG −τ−)}(17)with τ0,τ±(p )smooth,thenU −10(τ)α±p U 0(τ)=α±−ipτ∓(p ),U −1(τ)d dα±p∓i 2π)2τ±(p ),(p >0).The composition law for the operators U 0isU 0(τ(1))U 0(τ(2))=exp {2πiω2(τ(1),τ(2))}U 0(τ(1)+τ(2)),whereω2(τ(1),τ(2))≡−i2π¯h )2p>0p (τ(1)−τ(2)+−τ(1)+τ(2)−)is a 2-cocycle of the gauge group algebra.Thus for N =±1we are dealing with a projectiverepresentation.The 2-cocycle ω2(τ(1),τ(2))is trivial,since it can be removed by a simple redeﬁnition of U 0(τ).Indeed,the modiﬁed operators˜U0(τ)=exp {i 2πα1(γ;τ)}·U 0(τ),(18)whereα1(γ,τ)≡−12π¯h )2p>0(α−p τ−−αp τ+)is a 1-cocycle,satisfy the ordinary composition law˜U0(τ(1))˜U 0(τ(2))=˜U 0(τ(1)+τ(2)),i.e.the action of the topologically trivial gauge transformations represented by 18is unitary.The modiﬁed Gauss law generators corresponding to 18areˆ˜G±(p )=ˆG ±(p )±18π2α±p .(19)The generators ˆ˜G±(p )commute:[ˆ˜G+(p ),ˆ˜G −(q )]−=0.This means that Gauss law can be maintained at the quantum level for N=±1,too.We deﬁne physical states as those which are annihilated byˆ˜G±(p)[11]:ˆ˜G(p)|phys;A =0.(20)±The zero componentˆG0is a sum of quantum generators of the global gauge transformations of the right-handed and left-handed fermionicﬁelds,so the other quantum constraints are:ρ±(0):|phys;A =0.(21) It follows from20that the physical states|phys;A respond to a gauge transformation from the zero topological class with a phase:U0(τ)|phys;A =exp{−i2πα1(γ;τ)}|phys;A .(22) Only for models without anomaly,i.e.for N=±1,this equation translates into the statement that physical states are gauge invariant.Equation22expresses in an exact form the nature of anomaly in the CSM.At the quantum level the gauge invariance is not broken,but realized projectively.The1-cocycleα1occuring in the projective representation contributes to the commutator of the Gauss law generators by a Schwinger term and produces therefore the anomaly.3.2Adiabatic ApproachLet us show now that we can come to the quantum constraints20and21in a diﬀerent way,using the adiabatic approximation[23,24].In the adiabatic approach,the dynamical variables are divided into two sets,one which we call fast variables and the other which we call slow variables.In our case, we treat the fermions as fast variables and the gaugeﬁelds as slow variables.Let A1be a manifold of all static gaugeﬁeld conﬁgurations A1(x).On A1a time-dependent gaugeﬁeld A1(x,t)corresponds to a path and a periodic gaugeﬁeld to a closed loop.We consider the fermionic part of the second-quantized Hamiltonian:ˆH F:which depends on t through the background gaugeﬁeld A1and so changes very slowly with time.We consider next the periodic gaugeﬁeld A1(x,t)(0≤t<T).After a time T the periodicﬁeld A1(x,t)returns to its original value:A1(x,0)=A1(x,T),so that:ˆH F:(0)=:ˆH F:(T).At each instant t we deﬁne eigenstates for:ˆH F:(t)by:ˆH F:(t)|F,A(t) =εF(t)|F,A(t) .The state|F=0,A(t) ≡|vac,A(t) is a ground state of:ˆH F:(t),:ˆH F:(t)|vac,A(t) =0.The Fock states|F,A(t) depend on t only through their implicit dependence on A1.They are assumed to be periodic in time,|F,A(T) =|F,A(0) ,orthonormalized,F′,A(t)|F,A(t) =δF,F′,and nondegenerate.The time evolution of the wave function of our system(fermions in a background gaugeﬁeld)is clearly governed by the Schrodinger equation:∂ψ(t)i¯h¯h T0dt·εF(t),whileT0dt L/2−L/2dx˙A1(x,t) F,A(t)|iδγBerryF≡δA1(x,t)|F,A(t) ,(24) then= T0dt L/2−L/2dx˙A1(x,t)A F(x,t).γBerryFWe see that upon parallel transport around a closed loop on A1the Fock state|F,A(t) acquiresan additional phase which is integrated exponential of A F(x,t).Whereas the dynamical phaseγdynF provides information about the duration of the evolution,the Berry’s phase reﬂects the nontrivial holonomy of the Fock states on A1.However,a direct computation of the diagonal matrix elements ofδδδA1(x,t)A F(y,t)−2π2¯h2 n>01L n(x−y))=(1−N2)e2+2ǫ(x−y)−1The corresponding U(1)connection is easily deduced asA F=0(x,t)=−12 T0dt L/2−L/2dx L/2−L/2dy˙A1(x,t)F F=0(x,y,t)A1(y,t).In terms of the Fourier components,the connection A F=0is rewritten as vac,A(t)|ddα±p(t)|vac,A(t) ≡A±(p,t)=±(1−N2)e2+L2pα∓p,so the nonvanishing curvature isF+−(p)≡d dαpA−=(1−N2)e2+L2p.A parallel transportation of the vacuum|vac,A(t) around a closed loop in(αp,α−p)–space(p>0) yields back the same vacuum state multiplied by the phaseγBerry F=0=(1−N2)e2+L2piαp˙α−p.This phase is associated with the projective representation of the gauge group.For N=±1,when the representation is unitary,the curvature F+−and the Berry phase vanish.As mentioned in the beginning of this Section,the projective representation is trivial and the2-cocycle in the composition law of the gauge transformation operators can be removed by a redeﬁnition of these operators.Analogously,if we redeﬁne the momentum operators asddα±p≡d8π2¯h21 dα±p|vac,A(t) =0,˜F+−=˜ddαp˜A−=0.However,the nonvanishing curvature F+−(p)shows itself in the algebra of the modiﬁed momentum operators which are noncommuting:[˜ddα−q]−=F+−(p)δp,q.Following27,we modify the Gauss law generators asˆG ±(p)−→ˆ˜G±(p)=¯h p˜d2πρN(±p)that coincides with19.The modiﬁed Gauss law generators have vanishing vacuum expectation values,vac,A(t)|ˆ˜G±(p,t)|vac,A(t) =0.This justiﬁes the deﬁnition20.For the zero componentˆG0,the vacuum expectation valuevac,A(t)|ˆG0|vac,A(t) =−12(e+η++e−η−)=1The quantum theory consistently describing the dynamics of the CSM should be deﬁnitely compatible with20.The corresponding quantum Hamiltonian is then deﬁned by the conditions[ˆ˜H,ˆ˜G±(p)]−=0(p>0)(29)which specify thatˆ˜H must be invariant under the modiﬁed topologically trivial gauge transformations generated byˆ˜G±(p).We have in29a system of non-homogeneous equations in the Lagrange multipliersˆv H,±which become operators at the quantum level.The solution of these equations isˆv H,±(p)=¯hp2{pd4π¯h)2α∓p}.Substituting this expression forˆv H,±(p)into the quantum counterpart of28,on the physical states |phys;A we obtain1L2¯h2 p>0(d dα−p−1dαp,˜ddα±by˜d2L ˆπ2b−1dαp,˜d2Lˆπ2b+V(ρN;ρN),whereV(ρN;ρN)≡e2+Lp2ρN(−p)ρN(p)is the energy of the Coulomb current-current interaction.In order to make the dependence on N for the Hamiltonian more obvious,let us representρN asρN=12(1−N)σ,whereρ≡ρ1=ρ++ρ−,σ≡ρ−1=ρ+−ρ−,and[ρ(p),ρ(q)]−=[σ(p),σ(q)]−=0,[σ(p),ρ(q)]−=2pδp,−q.Then the Coulomb interaction energy takes the formV(ρN;ρN)=14(1−N)2V(σ;σ)+12Lˆπ2b+V(ρ;ρ).For N=−1,the momentum space electric charge density operator isσ(p)andˆ˜H EM =12π¯h:[e+b L2π¯h]+n,ˆψ+→exp{i2πn2π¯h ]→[e−b LLx}ˆψ−.The action of the topologically nontrivial gauge transformations on the states can be represented by the operatorsU n=exp{−i2π¯h ]−2πd[e+b L nρN(n)and U0is given by17.To identify the gauge transformation as belonging to the n th topological class we use the index n in31.The case n=0corresponds to the topologically trivial gauge transformations.The topologically nontrivial gauge transformation operators satisfy the same composition law as the topologically trivial ones.The modiﬁed operators are˜U n =exp{−i¯hˆTb})n|phys;A .Among all states|phys;A one may identify the eigenstates of the operators of the physical variables.The action of the topologically nontrivial gauge transformations on such states may, generally speaking,change only the phase of these states by a C–number,since with any gauge transformations both topologically trivial and nontrivial,the operators of the physical variables and the observables cannot be ing|phys;θ to designate these physical states,we haveexp{∓i¯h ˆTb})n|phys;A(so calledθ–states[26,27]),where|phys;A is an arbitrary physical state from20.In one dimension the parameterθis related to a constant background electricﬁeld.To show this, let us introduce states which are invariant even against the topologically nontrivial gauge transfor-mations.Recalling that[e+b L2π¯h]θ}|phys;θ .(32)The new states|phys continue to be annihilated byˆ˜G±(p),and are also invariant under the topo-logically nontrivial gauge transformations.The electromagnetic part of the Hamiltonian transforms asˆHEM→exp{i[e+b L2π¯h]θ}=12L¯h2 p>0[˜d dα−p]+,i.e.in the new Hamiltonian the momentumˆπb is supplemented by the electricﬁeld strength Eθ≡e+The condition34can be then rewritten as a system of linear equations in(β0,β±).We can easilyﬁnd a solution of these equations,which gives us(β0,β±)as functions of[e+b L2π¯h}.However,these constants are irrelevant for our consideration and we neglect them.Finding(β0,β±)from34and substituting them into the expression33,on the physical states we obtainˆ˜H|phys;A =ˆHphys|phys;AwhereˆH phys =ˆH physF+ˆH physEM,ˆH physF=ˆH0,++ˆH0,−−1L¯h(1+N2)([e+b LL ¯h[e+b L2L ˆπ2b+V(ρN;ρN)+e2+L2π¯h] p∈Z p=0(−1)p 24(1−N2)2([e+b LL¯h p>0|λεp,±|−sρs±(−p)ρs±(p).Eqs.35and36give us a physical Hamiltonian invariant under both topologically trivial andnontrivial gauge transformations,ˆH physF andˆH physEMbeing invariant separately.The last two terms in35make invariant the free fermionic part of the Hamiltonian,while the ones in36the electromagnetic part.For N=±1,the last two terms in36vanish.These terms are therefore caused by the anomaly and represent new types of interaction which are absent in the nonanomalous models.The new interactions admit the following interpretation.Let us combine the last term in36with the kinetic part of the electromagnetic Hamiltonian,then124(1−N2)2([e+b L2L2 L/2−L/2dx(ˆπb−L E(x))2,i.e.the momentumˆπb is supplemented by the linearly rising electricﬁeld strengthE(x)≡−e+2π¯h].As in four-dimensional models of a relativistic particle moving in an externalﬁeld,we may deﬁne a generalized momentum operator in the formˆ˜πb(x)≡ˆπb−L E(x).The commutation relations for ˆ˜πb are[ˆ˜πb (x ),ˆ˜πb (y )]−=i (1−N 2)e 2+LL(1−N 2)[e +b L2L 2ˆ˜π2b→14π2(1−N 2)[e +b Lp 2ρN (p )=−e 2+L2p 2ρbgrd ·ρN (p ).It is just the background linearly rising electric ﬁeld that couples b to the fermionic physical degreesof freedom in the Coulomb interaction.As a consequence,the eigenstates of the physical Hamiltonian are not a direct product of the purely fermionic Fock states and wave functionals of b .This is a common feature of gauge theories with anomaly.That the Hilbert space in such theories is not a tensor product of the Hilbert space for a gauge ﬁeld and the ﬁxed Hilbert space for fermions was shown in [6],[7].The background charge interpretation is related to the deﬁnition of the Fock vacuum.The deﬁnition given in Eqs.10-11depends on [e +b L2π¯h]is ﬁxed.The values of the gauge ﬁeld in regions of diﬀerent [e +b L2π¯h]changes,then there is a nontrivial spectral ﬂow,i.e.some of energy levels of the ﬁrst quantized fermionic Hamiltonians cross zero and change sign.This means that the deﬁnition of the Fock vacuum changes.The charge operators ˆQ ±also change.Let :ˆQ (0)±:be charge operators deﬁned in the region where[e +b L 2π¯h]the charge operators become :ˆQ (0)±:∓e ±[e ±b L。

大学英语专业语法课件3-限定词Determ

• Quantifiers: Quantifiers are words or phrases that indicate the quantity or amount of something. Common quantifiers include words such as "many," "few," "several," "a lot of," etc.
Types of determiners: There are different types of determiners, including articles, demonstratives ("this," "that," "these," "those"), quantifiers ("some," "any," "many," "few"), and possessives, each serving a specific function in relation to the noun.
Classification
Qualifiers can be divided into two main categories: adjectives and adverbs. Adjectives modify nouns or pronouns, adding descriptive details such as color, size, shape, age, etc. Adverbs modify verbs, adjectives, or other adverbs, adding details such as time, place, manner, degree, etc.

Study_on_the_Pretreatment_Methods_for_the_Detectio

Creativity and Innovation2022,VOL.6,NO.5,75-80DOI:10.47297/wspciWSP2516-252712.20220605Study on the Pretreatment Methods for the Detection of Heavy Metal Stress in Shellfish by Hyperspectral TechnologyShuwen Wang2*,Jibin Zhang1,Hengjun Jiang1,Wenjun Xie1,Fengliang Chen11School of Electronic and Electrical Engineering,Lingnan Normal University,Zhanjiang,Guangdong2College of Computer and Intelligent Education,Lingnan Normal University,Zhanjiang,GuangdongABSTRACTIn this paper,hyperspectral technology was combined with differentoptimized pretreatment methods to construct a non-destructiveidentification method for cadmium contaminated and normal Ruditapesphilippinarum.Firstly,120samples of normal and heavy metal cadmiumpollution were collected,and their hyperspectral curves were compared,and then the optimization effects of different preprocessing methods onthe original spectra were explored,and finally the processing results wereused as the input of extreme learning machine classifier to screen out thebest preprocessing method.The results show that the use of SGsmoothing,multiplicative scatter correction(MSC),standard normalvariate transformation(SNVT),first derivative,second derivative and theircombination optimization methods is beneficial to the discrimination ofdifferent classes of spectral curves to a certain extent.Finally,theclassification accuracy of the extreme learning machine classifier is usedas the evaluation index to determine that the multiplicative scattercorrection preprocessing method is the optimal spectral preprocessingmethod.KEYWORDSHyperspectral image;Heavy metal cadmium;Pretreated Ruditapesphilippinensis1Research BackgroundRuditapes philippinarum is one of the main shellfish cultured along the coast.It is rich in various amino acids,vitamins and essential trace elements for human body.It has high nutritional value and delicious taste,so it is very popular[1].In recent years,with the rapid development of industry,a large number of pollutants are directly discharged into the sea,resulting in the aggravation of marine environmental pollution.Cadmium (Cd)is a typical harmful element which is easy to accumulate in organisms and difficult to metabolize,and widely exists in the natural environment[2].Ruditapes philippinarum is widely distributed in coastal areas with relatively serious heavy metal pollution.As a non-selective filter-feeding organism,Ruditapes philippinarum will accumulate heavy metal pollutants in sediments and water during feeding.Long-term consumption of heavy metal contaminated Ruditapes*Corresponding Author:Shuwen Wang(1975-04),male,Han,Zhaodong City,Heilongjiang Province,graduatestudent,associate professor,Interest:Application of intelligent measurement and controltechnology.Shuwen Wang et al. philippinarum will cause harm to human health[3].Therefore,it has become an urgent problem to improve the detection ability of heavy metal pollution in Ruditapes philippinarum and ensure the quality and food safety of Ruditapes philippinarum in food safety science.Aiming at the spectral interference and noise generated in the process of hyperspectral image acquisition of Ruditapes philippinarum,this paper studies the elimination of interference factors by different preprocessing methods,and explores the optimization effect of different single and combined preprocessing methods on the interference in the hyperspectral data of Ruditapes philippinarum[4].Finally,the extreme learning machine was used to realize the rapid non-destructive detection and analysis[5]of normal samples and heavy metal cadmium contaminated samples of Ruditapes philippinarum,and the optimal pretreatment method was determined according to the classification detection results.2Test Materials and Research Methods(1)Culture of test samplesThe samples of Ruditapes philippinarum were purchased from Cunjin Seafood Market,Zhanjiang City,Guangdong Province.The fine sand was disinfected to remove impurities and laid in a plastic culture box with a size of119cm×108cm×32cm and a volume of300L.Seawater was allowed to settle for24hours and then filtered for laboratory culture of Ruditapes philippinarum samples.The pH value of the sea water is8.0,the water temperature is28℃,the dissolved oxygen content is6.5mg/L,and the salinity is30‰.CdC12·2.5H2O solution with a concentration of0.8mg/L-1was addedinto the culture box to simulate the marine environment polluted by heavy metal cadmium.The control group was raised in seawater without any heavy metal elements.During the experiment,thefilter was closed for4hours every day,during which Chlorella was fed.Seawater containing CdC12·2.5H2O reagent and pure seawater were added to the two culture tanks every day to supplementthe loss of seawater in the culture tanks.The Ruditapes philippinarum samples were incubated in a culture box for10days to allow for the accumulation of the heavy metal cadmium.At the end of the culture,60cadmium contaminated samples and60uncontaminated samples of Ruditapes philippinarum were collected for hyperspectral image acquisition[6].(2)Hyperspectral image acquisitionIn this study,the hyperspectral imaging data of Ruditapes philippinarum samples were collected by SOC710-VP hyperspectral imager produced by Surface Optics Company in the United States.The system consists of a hyperspectral imager,a light source unit(halogen lamp),and a carrier plaorm unit(25),as shown in Figure1.The hyperspectral imager has an acquisition range of367.7-1051.9 nm with512bands.The spectrum at the front and end of the whole spectral range contains a lot of noise,so these two parts of the spectrum are removed,and450spectral bands from400.5nm to 1000.9nm are retained.The standard calibration of hyperspectral images,including spectral calibration,radiometric calibration,and reflectance normalization,is performed in SRAnal710 software.Fig.2is a hyperspectral image of Ruditapes philippinarum contaminated by heavy metal cadmium.76Creativity and Innovation 3Results and AnalysisFig.3shows the original spectrum of the Ruditapes philippinarum sample and the spectral curve pretreated by SG smoothing,multiplicative scatter correction (MSC),standard normal variate (SNV),first derivative (FD),second derivative (SD)and their various pretreatment combination optimizationmethods.(A)Rawspectrum (b)SGFig.1Hyperspectral image acquisitionsystemFig.2Hyperspectral image of Ruditapes philippinarum77Shuwen Wang etal.(c)MSC(e)FD(g)SG-FD (d)SNV (f)SD (h)SG-SD78Creativity andInnovation (i)MSC-FD (k)SNV-FD (j)MSC-SD(l)SNV-SDFig.3Spectral curves of Ruditapes philippinarum under various pretreatment methods and different combinations 60healthy samples and 60cadmium contaminated samples after spectral preprocessing are taken as experimental data sets,45samples of each class of samples are taken as training data sets,15samples are taken as test data sets,and the extreme learning machine classifier is used for classification.Because of the random selection,in order to reduce the random error,the modeling was repeated 500times each time,and the classification effect was evaluated by the average of the classification accuracy of the 500experimental results.The corresponding average classification accuracies of SG,MSC,SNV,FD,SD and their SG-FD,SG-SD,MSC-FD,MSC-SD,SNV-FD,SNV-SD preconditioning methods were 92.35%,95.25%,88.93%,91.89%,91.89%,83.99%、90.36%、93.93%、89.96%、88.94%、84.50%。

下载提示

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Petri网

页数:21
基于时间Petri网的物流系统建模与仿真实例

页数:2
课时作业1：Grammar—Past participles as the predicative

页数:7
时标网络计划

页数:15
Time Management Skills

页数:2
高级Petri网的测试方法研究

页数:4
时标网络计划

页数:1
时标网络计划

页数:19
基于Petri网的语义Web服务组合方法

页数:8
Time Management Skills

页数:2
managementobjectsearcher time consuming

页数:6
TimeManagementPPT课件

页数:46

Generalized State Classes of Time Petri Nets for Timeliness Analysis

合集下载

Predicate Classes, Promise Classes, and the Acceptance Power of Regular Languages

Generalised chiral QED2 Anomaly and Exotic Statistics

大学英语专业语法课件3-限定词Determ

Study_on_the_Pretreatment_Methods_for_the_Detectio

文档推荐

最新文档