發(fā)布時(shí)間：2018-04-28 19:16

  本文選題：多項(xiàng)式代數(shù)事件結(jié)構(gòu) + 近似　； 參考：《北京交通大學(xué)》2016年博士論文

【摘要】：近年來(lái),并發(fā)系統(tǒng)有著頗為廣泛的應(yīng)用。事件結(jié)構(gòu)作為并發(fā)系統(tǒng)的語(yǔ)義模型之一,引起了理論與工程學(xué)界極大的關(guān)注和興趣,并吸引了大量的學(xué)者進(jìn)行研究。傳統(tǒng)的事件結(jié)構(gòu)建立在抽象動(dòng)作符號(hào)集合之上,但抽象的動(dòng)作不能細(xì)致地描述系統(tǒng)行為,也不能處理近似問(wèn)題。然而,近似問(wèn)題在工程應(yīng)用中卻是非常常見(jiàn)。例如,在實(shí)際測(cè)量和計(jì)算過(guò)程中,測(cè)量誤差和截?cái)嗾`差經(jīng)常是不可避免的,這意味著經(jīng)常無(wú)法獲得完全精確的解。實(shí)際上,工程問(wèn)題的解并不總是精度越高越好,還需要平衡好精度與時(shí)間復(fù)雜度、空間復(fù)雜度的關(guān)系,換言之,完全精確的解有時(shí)也是不必要的。此外,近似還經(jīng)常應(yīng)用于以下兩方面：一是簡(jiǎn)化系統(tǒng),在預(yù)先給定的可以容忍的誤差范圍內(nèi),對(duì)原始系統(tǒng)進(jìn)行近似化簡(jiǎn),從而得到一個(gè)復(fù)雜度降低的簡(jiǎn)化系統(tǒng);二是擴(kuò)展系統(tǒng)之間的傳統(tǒng)精確等價(jià)關(guān)系,通常把兩個(gè)系統(tǒng)之間的近似程度解讀為距離,從而可以將兩個(gè)系統(tǒng)之間的傳統(tǒng)精確等價(jià)關(guān)系擴(kuò)展為具有魯棒性的近似等價(jià)關(guān)系。因此,如果要將傳統(tǒng)事件結(jié)構(gòu)的應(yīng)用擴(kuò)展到更廣的領(lǐng)域,有必要將事件結(jié)構(gòu)擴(kuò)展以處理近似問(wèn)題。在并發(fā)系統(tǒng)模型理論中,系統(tǒng)的簡(jiǎn)化問(wèn)題是核心問(wèn)題之一。在進(jìn)行系統(tǒng)簡(jiǎn)化時(shí),語(yǔ)義等價(jià)是最常用的方法之一。目前已經(jīng)有大量的學(xué)者對(duì)語(yǔ)義等價(jià)進(jìn)行研究,并且形成了完整的理論體系。語(yǔ)義等價(jià)分為線性時(shí)間等價(jià)和分支時(shí)間等價(jià)兩類。線性時(shí)間等價(jià)主要包括跡等價(jià),分支時(shí)間等價(jià)主要包括(單元)失敗等價(jià)和互模擬等價(jià)。但是目前跡等價(jià)、(單元)失敗等價(jià)和互模擬等價(jià)主要應(yīng)用于標(biāo)簽變遷系統(tǒng)的化簡(jiǎn),極少應(yīng)用于事件結(jié)構(gòu)的化簡(jiǎn)。實(shí)際上,目前事件結(jié)構(gòu)上(近似)語(yǔ)義等價(jià)理論尚不健全,如何將語(yǔ)義等價(jià)應(yīng)用于事件結(jié)構(gòu)的理論研究成為需要深入研究的重要問(wèn)題。為了解決以上問(wèn)題,本文在傳統(tǒng)的事件結(jié)構(gòu)中引入多項(xiàng)式代數(shù),提出了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的概念。由多項(xiàng)式代數(shù)事件結(jié)構(gòu)誘導(dǎo)出對(duì)應(yīng)的多項(xiàng)式代數(shù)交織標(biāo)簽變遷系統(tǒng)和多項(xiàng)式代數(shù)步進(jìn)標(biāo)簽變遷系統(tǒng),從而使得線性時(shí)間-分支時(shí)間等價(jià)譜系理論可以應(yīng)用于多項(xiàng)式代數(shù)事件結(jié)構(gòu),最終建立了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的近似和近似等價(jià)理論.具體地,本文的研究方法和主要成果如下：1)提出了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的概念,并使用兩種不同的構(gòu)造方法,將傳統(tǒng)事件結(jié)構(gòu)轉(zhuǎn)化為多項(xiàng)式代數(shù)事件結(jié)構(gòu),驗(yàn)證了傳統(tǒng)事件結(jié)構(gòu)是多項(xiàng)式代數(shù)事件結(jié)構(gòu)的特例。2)討論了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的刻畫能力,舉例并分析了如何應(yīng)用多項(xiàng)式代數(shù)事件結(jié)構(gòu)刻畫計(jì)算機(jī)程序。在分析過(guò)程中,本文發(fā)現(xiàn)在五種經(jīng)典事件結(jié)構(gòu)(基本事件結(jié)構(gòu)、穩(wěn)定事件結(jié)構(gòu)、流事件結(jié)構(gòu)、集束事件結(jié)構(gòu)和擴(kuò)展集束事件結(jié)構(gòu))中,流事件結(jié)構(gòu)最適合作為程序的模型。3)重點(diǎn)研究了事件結(jié)構(gòu)并行特性中的交織語(yǔ)義和步進(jìn)語(yǔ)義。結(jié)合事件結(jié)構(gòu)的格局結(jié)構(gòu)定義,由多項(xiàng)式代數(shù)事件結(jié)構(gòu)可以誘導(dǎo)出多項(xiàng)式代數(shù)交織標(biāo)簽變遷系統(tǒng)和多項(xiàng)式代數(shù)步進(jìn)標(biāo)簽變遷系統(tǒng),從而使得線性時(shí)間-分支時(shí)間等價(jià)譜系理論可以應(yīng)用于多項(xiàng)式代數(shù)事件結(jié)構(gòu)。4)在線性時(shí)間-分支時(shí)間等價(jià)譜系理論的研究中,本文分別討論了可達(dá)性等價(jià)、跡等價(jià)、失敗等價(jià)、單元失敗等價(jià)和互模擬等價(jià)。其中,根據(jù)是否引入觀測(cè)值,將所有語(yǔ)義等價(jià)分成基于跡和基于可見(jiàn)跡兩個(gè)子類。值得一提的是,本文提出了最小單元失敗集合的概念,并證明了最小單元失敗集合方法在所有能判定單元失敗等價(jià)的方法中是最優(yōu)的。因此,運(yùn)用最小單元失敗集合方法可以極大地簡(jiǎn)化單元失敗等價(jià)的驗(yàn)證計(jì)算。本文分別對(duì)一個(gè)規(guī)模較小的實(shí)例和一個(gè)規(guī)模較大的實(shí)例進(jìn)行分析,結(jié)果顯示使用最小單元失敗集合方法比傳統(tǒng)方法判定單元失敗等價(jià)減少了較多的工作量。5)構(gòu)建了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的近似理論。一方面,結(jié)合實(shí)例分別運(yùn)用了泰勒展開、最佳一次逼近和分段線性插值等數(shù)值近似理論近似化簡(jiǎn)多項(xiàng)式代數(shù)事件結(jié)構(gòu),并在實(shí)例中探討了誤差傳遞問(wèn)題。另一方面,給多項(xiàng)式代數(shù)事件結(jié)構(gòu)誘導(dǎo)出的多項(xiàng)式代數(shù)標(biāo)簽變遷系統(tǒng)賦予Baire度量,并結(jié)合豪斯多夫距離,以及跡集合和互模擬關(guān)系的定義,給出跡距離函數(shù)和互模擬距離函數(shù),從而量化了多項(xiàng)式代數(shù)事件結(jié)構(gòu)之間的近似關(guān)系。6)構(gòu)建了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的近似等價(jià)理論。本文創(chuàng)新性地引入弱化了的Baire度量,使得得到的度量具有傳遞性性質(zhì)。然后結(jié)合豪斯多夫距離,定義了多項(xiàng)式代數(shù)事件結(jié)構(gòu)的近似跡等價(jià)和近似單元失敗等價(jià)。如果假設(shè)觀測(cè)值空間為n維空間,類似地,就可以得到多項(xiàng)式代數(shù)事件結(jié)構(gòu)的近似可達(dá)性等價(jià)和近似互模擬等價(jià)定義。這些近似等價(jià)都具有傳遞性,因此可以多次運(yùn)用這些近似等價(jià)來(lái)化簡(jiǎn)模型,并且各個(gè)傳統(tǒng)精確等價(jià)是對(duì)應(yīng)的近似等價(jià)的特例。這些近似等價(jià)之間的粗糙關(guān)系與傳統(tǒng)精確等價(jià)之間的粗糙關(guān)系保持一致。綜上所述,多項(xiàng)式代數(shù)事件結(jié)構(gòu)能夠更細(xì)致地刻畫系統(tǒng)行為,并且可以處理近似問(wèn)題。雖然多項(xiàng)式代數(shù)事件結(jié)構(gòu)較傳統(tǒng)事件結(jié)構(gòu)數(shù)學(xué)形式更復(fù)雜,但是多項(xiàng)式代數(shù)事件結(jié)構(gòu)也因此可以運(yùn)用數(shù)值近似理論進(jìn)行化簡(jiǎn)。本文提出的多項(xiàng)式代數(shù)事件結(jié)構(gòu)以及建立的多項(xiàng)式代數(shù)事件結(jié)構(gòu)近似和近似等價(jià)理論,將為并發(fā)系統(tǒng)的研究提供有力支撐。
[Abstract]:In recent years, concurrent systems have been widely used. As one of the semantic models of concurrent systems, event structures have aroused great concern and interest in the field of theory and engineering, and attracted a large number of scholars to study. The traditional event structure is based on the combination of abstract action symbols, but the abstract action can not be described in detail. System behavior can not deal with approximate problems. However, approximate problems are very common in engineering applications. For example, in actual measurement and calculation, the measurement error and truncation error are often unavoidable, which means that the exact solutions are often not obtained. In practice, the solution of the engineering problem is not always the better, the better the accuracy, It is also necessary to balance the complexity of precision and time and the complexity of space. In other words, the exact solution is sometimes unnecessary. In addition, the approximation is often used in the following two aspects: one is to simplify the system, to approximate the original system in the range of tolerable errors in advance, so as to get a complexity. Reduced simplified systems; two is the traditional exact equivalence relation between extended systems, which usually interprets the approximate degree between the two systems as distance, so that the traditional exact equivalence relation between the two systems can be extended to a robust approximate equivalence relation. Therefore, the application of the traditional event structure should be extended to a wider range. It is necessary to expand the event structure to deal with the approximate problem. In the theory of concurrent system model, the problem of simplification of the system is one of the core problems. In the process of system simplification, semantic equivalence is one of the most commonly used methods. At present, a large number of scholars have studied semantic equivalence and formed a complete theoretical system. Semantic equivalence is divided into two categories: linear time equivalence and branch time equivalence. Linear time equivalence mainly includes trace equivalence, and branch time equivalence mainly includes (element) failure equivalence and mutual simulation equivalence. However, the equivalence of trace, (element) failure equivalence and intersimulation equivalence are mainly used in the simplification of label transition systems, and rarely should be used in event junctions. In fact, the theory of semantic equivalence is not perfect at present. How to apply semantic equivalence to the theoretical study of event structure has become an important problem. In order to solve the above problems, this paper introduces polynomial algebra in the traditional event structure, and proposes the structure of polynomial algebraic events. A polynomial algebraic interlaced label transition system and a polynomial algebraic step label transition system are derived from the polynomial algebraic event structure. The linear time branch time equivalence pedigree theory can be applied to the polynomial algebraic event structure, and the approximation and approximation of the polynomial algebraic event structure are finally established. In particular, the research methods and main achievements of this paper are as follows: 1) the concept of polynomial algebraic event structure is proposed, and two different construction methods are used to transform the traditional event structure into a polynomial algebraic event structure, and the traditional event structure is a special case.2 of multiple algebraic event structures. In the analysis process, we find that the flow event structure is most suitable for the five classical event structures (basic event structure, stable event structure, flow event structure, cluster event structure, and extended cluster event structure). As a model.3 of the program, we focus on the study of interleaving semantics and step semantics in the parallel characteristics of event structures. Combining the pattern structure definition of event structure, polynomial algebraic interlaced label transition system and polynomial algebraic step label transition system can be induced by the structure definition of the event structure, so that the linear time - branching time is made. The theory of inter equivalence pedigree can be applied to the polynomial algebraic event structure.4) in the study of linear time branch time equivalence pedigree theory. The equivalence of accessibility, trace equivalence, failure equivalence, unit failure equivalence and mutual simulation equivalence are discussed respectively in this paper. In this paper, all the semantic equivalence is divided into trace and base based on whether the observation value is introduced. It is worth mentioning that the concept of the minimum unit failure set is proposed in this paper, and it is proved that the minimum unit failure set method is optimal in all the methods of the failure equivalence of the determinant unit. Therefore, the minimum unit failure set method can greatly simplify the verification calculation of the unit failure equivalence. In this paper, a smaller example and a larger example are analyzed. The results show that the minimum unit failure set method is equivalent to the failure of the traditional method decision unit to reduce the amount of work.5.) the approximate theory of the polynomial algebraic event structure is constructed. On the one hand, the Taylor Exhibition is applied to the example with an example. The optimal one approximation and piecewise linear interpolation are used to approximate the structure of the polynomial algebraic events, and the problem of error transfer is discussed in an example. On the other hand, the polynomial algebraic label transition system is given to the polynomial algebraic event structure to give the Baire degree, combined with Moorhouse's multi Fu distance, and the trace set and the trace set. The definition of the intersimulation relationship, gives the trace distance function and the cross simulation distance function, thus quantifies the approximate relation between the polynomial algebraic event structures.6) and constructs the approximate equivalence theory of the polynomial algebraic event structure. This paper innovatively introduces the weakening of the Baire metric to make the obtained metric with transitive properties. Moorhouse's multi - husband distance defines the equivalent of the approximate trace of the polynomial algebraic event structure and the equivalence of the approximation unit failure. If the observational value space is n dimensional space, the approximate equivalence of the polynomial algebraic event structure and the equivalent mutual simulation equivalence definition can be obtained. These approximate equivalence all have transitivity, so they can be transitive. Many of these approximate equivalence is used to simplify the simplified model, and the traditional exact equivalence is a special case of the corresponding equivalent. The rough relations between these approximate equivalence are consistent with the rough relations between the traditional exact equivalence. To sum up, the polynomial algebraic event structure can depict the system behavior more carefully, and can be dealt with. Although the structure of polynomial algebraic events is more complex than the traditional event structure mathematical form, the structure of polynomial algebraic events can be reduced by numerical approximation theory. The structure of polynomial algebraic events and the structure approximation and approximate equivalence theory of polynomial algebraic events proposed in this paper will be concurrency. The research of the system provides a strong support.

【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O174.14

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉建福,徐德啟;并發(fā)系統(tǒng)的模型與驗(yàn)證[J];蘭州大學(xué)學(xué)報(bào);1992年01期

2 蔣昌俊，，鄭應(yīng)平，疏松桂;并發(fā)系統(tǒng)建模與分析研究[J];高技術(shù)通訊;1996年06期

3 張廣泉;并發(fā)系統(tǒng)性質(zhì)驗(yàn)證的一種形式化方法[J];重慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1999年03期

4 桂志波,齊延信;弱引發(fā)三態(tài)加時(shí)變遷Petri網(wǎng)及其在并發(fā)系統(tǒng)中應(yīng)用[J];應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào);1999年01期

5 蔣昌俊,祝明發(fā),李國(guó)杰;合成網(wǎng)的進(jìn)程語(yǔ)義[J];應(yīng)用科學(xué)學(xué)報(bào);2000年01期

6 張廣泉,戎玫;并發(fā)系統(tǒng)性質(zhì)描述的一種形式化方法[J];重慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);1998年01期

7 蔣昌俊,鄭應(yīng)平,閆春鋼;Petri網(wǎng)的組合操作及其在并發(fā)系統(tǒng)綜合建模中的應(yīng)用[J];系統(tǒng)工程學(xué)報(bào);1996年04期

8 蔣昌俊,張兆慶,喬如良;基于Petri網(wǎng)的并發(fā)系統(tǒng)控制器設(shè)計(jì)[J];系統(tǒng)工程學(xué)報(bào);2001年02期

9 倫立軍,劉志紅;哲學(xué)家就餐問(wèn)題的Petri網(wǎng)描述[J];哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào);1999年05期

10 ;[J];;年期

相關(guān)會(huì)議論文 前4條

1 燕飛;唐濤;;實(shí)時(shí)并發(fā)系統(tǒng)的形式化建模方法研究[A];2009系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2009年

2 陳曉江;楊琛;馮健;房鼎益;;并發(fā)系統(tǒng)模型檢測(cè)中的狀態(tài)約減算法[A];2007年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2007年

3 蔣昌俊;疏松桂;鄭應(yīng)平;;隨機(jī)Petri網(wǎng)同步并發(fā)行為的量化分析[A];1994中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1994年

4 朱連章;魏曉慧;;基于著色Petri網(wǎng)避免并發(fā)系統(tǒng)死鎖的方法[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

相關(guān)博士學(xué)位論文 前5條

1 夏默;并發(fā)系統(tǒng)的建模與驗(yàn)證一體化方法的研究[D];清華大學(xué);2015年

2 王超;多項(xiàng)式代數(shù)事件結(jié)構(gòu)及其近似和近似等價(jià)[D];北京交通大學(xué);2016年

3 蔣昌俊;并發(fā)系統(tǒng)綜合的PN行為理論及其應(yīng)用[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;1998年

4 吳鵬;并發(fā)系統(tǒng)的模型檢測(cè)與測(cè)試[D];中國(guó)科學(xué)院研究生院（軟件研究所）;2005年

5 鄭光;并發(fā)系統(tǒng)的動(dòng)作細(xì)化理論[D];蘭州大學(xué);2008年

相關(guān)碩士學(xué)位論文 前6條

1 王婷;基于偏序簡(jiǎn)化的并發(fā)系統(tǒng)模型檢測(cè)技術(shù)的研究[D];西北大學(xué);2007年

2 賀彥琨;并發(fā)系統(tǒng)的事件結(jié)構(gòu)模型初步研究[D];蘭州大學(xué);2008年

3 楊琛;基于進(jìn)程代數(shù)并發(fā)系統(tǒng)的建模與驗(yàn)證研究[D];西北大學(xué);2006年

4 宋琳;概率進(jìn)程演算的互模擬分析[D];上海交通大學(xué);2007年

5 申慧;并發(fā)系統(tǒng)的并行計(jì)算及性能分析[D];浙江理工大學(xué);2011年

6 宋磊;概率符號(hào)Pi演算的有限公理化[D];上海交通大學(xué);2009年

本文編號(hào)：1816527