P계통

P system
컴퓨터 p-시스템에 대한 내용은 UCSD p-시스템을 참조하십시오.

P시스템은 생물학적으로 영감을 받은 공정을 이용해 계산을 수행하는 컴퓨터 과학 분야의 연산 모델이다.그것들은 화학물질이 상호 작용하고 세포막을 가로지르는 방식에서 추출하여 생물학적 세포의 구조에 기초한다.이 개념은 컴퓨터 과학자인 게오르게 피춘의 1998년[1] 보고서에서 처음 소개되었는데, 그의 성은 'P 시스템'에서 문자 P의 기원이다.P 시스템 모델의 변화는 'membrane computing'이라고 알려진 연구 분과의 형성을 이끌었다.null

생물학에서 영감을 얻었지만, P 시스템에 대한 1차 연구 관심은 생물학적 모델링이 아닌 계산적 모델로 사용하는 것과 관련이 있지만,[2] 이것도 조사되고 있다.[3][4][5]null

비공식 설명

P 시스템은 화학 물질(유한 수량), 촉매 및 화학 물질이 서로 반응하여 제품을 형성할 수 있는 방법을 결정하는 일련의 막으로 정의된다.규칙들은 또한 화학물질이 막을 통과하게 하거나 심지어 막이 용해되게 할 수도 있다.null

생물학적 세포에서와 마찬가지로, 필요한 화학 분자가 충돌하고 상호작용하는 우연한 사건(아마도 촉매와 함께)에만 화학 반응이 일어날 수 있는 경우, P 시스템의 규칙은 무작위로 적용된다.이로 인해 연산이 결정적이지 않은 방식으로 진행되며, 연산이 반복될 경우 여러 해법이 발생하는 경우가 많다.null

P 시스템은 더 이상의 반응이 불가능한 상태에 도달할 때까지 계속된다.이 시점에서 계산의 결과는 가장 바깥쪽 막 밖으로 통과된 화학 물질 또는 지정된 '결과' 막으로 전달된 화학 물질이다.[4]null

P 시스템의 구성 요소

비록 많은 종류의 P 시스템이 존재하지만, 대부분은 동일한 기본 구성요소를 공유한다.각 원소는 특정한 역할을 가지고 있으며, 각 원소는 P 시스템의 기반이 되는 생물학적 세포 구조에 기반을 두고 있다.null

환경

환경은 P 시스템의 주변이다.P 시스템의 초기 상태에서는 컨테이너-membrane만 포함하고, 환경은 결코 규칙을 보유할 수 없지만, 그것은 계산하는 동안 그 안으로 물체가 전달될 수 있다.계산의 끝에 있는 환경 내에서 발견된 물체는 "결과"의 전부 또는 일부를 구성한다.null

막

막은 P 시스템 내의 주요 "구조물"이다.막은 물체 집합(심볼/촉매), 규칙 집합 및 그 안에 포함된 다른 막 집합을 포함할 수 있는 이산 단위다.가장 바깥쪽 막은 환경 안에서 잡히는 것을 흔히 '용기막' 또는 '피부막'이라고 부른다.그들의 이름에서 암시된 바와 같이, 막은 투과성이 있고 규칙에서 비롯되는 기호가 그것들을 가로지를 수 있다.막(그러나 용기 막은 아니다)도 "분해"될 수 있는데, 이 경우 (잃어버린) 규칙을 제외한 그 내용물은 그 막이 들어 있던 막으로 이동한다.[2]null

일부 P 시스템 변형에서는 막 두께를 변경하여 막이 분할되거나 전하를 가지거나 투과성이 다양할 수 있다.[2]null

기호

기호는 어떤 제품을 만들기 위해 다른 화학물질과 반응할 수 있는 화학물질을 나타낸다.P 시스템에서 각 기호의 유형은 일반적으로 다른 문자로 표현된다.따라서 막의 기호 함량은 일련의 문자로 표현된다.지역의 기호의 다양성이 중요하기 때문에, 멀티셋은 일반적으로 지역의 기호 내용을 나타내기 위해 사용된다.null

예를 들어 특수 사례 기호가 존재하며, 예를 들어, 낮은 사례 델타(Δ)는 종종 막의 용해를 시작하는 데 사용되며, 이것은 규칙의 출력에서만 발견된다. 즉, 마주쳤을 때 반응을 일으키며, 그 과정에서 사용된다.null

촉매

촉매들은 화학에서의 그들의 이름과 비슷하다.그것들은 상징과 같은 방법으로 표현되고 사용되지만, "반작용"하는 동안 결코 소비되지 않는다. 그것들은 단지 발생하기 위한 요구 사항일 뿐이다.null

규칙.

규칙은 막 안에서 일어날 수 있는 화학 반응을 나타내며, 막이 새로운 상태로 진화하는 원인이 된다.규칙에는 적용하기 위해 반드시 존재해야 하는 입력 객체(기호 또는 촉매)의 필수 집합이 있다.필요한 개체가 있으면 이를 소비하고 출력 개체 집합을 생성한다.규칙이 다른 규칙보다 우선하도록 지정할 수도 있는데, 이 경우 덜 지배적인 규칙은 더 지배적인 규칙을 적용할 수 없을 때(즉, 필요한 입력이 없을 때)에만 적용된다.null

(기본 P 시스템 모델에서) 규칙이 출력 객체를 처리할 수 있는 세 가지 뚜렷한 방법이 있다.일반적으로 출력 객체는 여기서 규칙으로 알려진 현재 막(규칙과 입력부가 상주하는 동일한 막)으로 전달된다.그러나 규칙이 정의될 때 출력 객체에 지정할 수 있는 두 개의 수식어가 있다.in 수식어는 물체가 계산 중에 무작위로 선택한 현재 막의 자식(P 시스템의 구조에 비례하여 안으로 이동) 중 하나에 전달되도록 한다.아웃 수식어는 물체가 현재 막에서 벗어나 그 모막 또는 형제막으로 전달되도록 하며, P 시스템의 사양 중에 지정된다.null

연산공정

계산은 초기 시작 상태에서 여러 개별 단계를 통해 엔드 상태로 작동한다.각 단계는 P 시스템의 모든 막과 규칙의 적용을 통해 반복하는 것을 포함하며, 이는 최대 병렬 및 비결정론적 방식으로 발생한다.[4]null

단계별 작업을 수행하면 더 이상의 진화가 일어날 수 없을 때(즉, 규칙을 적용할 수 없을 때) 계산이 중단된다.이 시점에서 환경 또는 지정된 '결과' 막으로 전달된 물체는 모두 계산 결과로 계산된다.[4]null

규칙 적용

계산의 각 단계에서 물체는 적용되었을 때 규칙에 의해 소비되기 때문에 한 번만 사용될 수 있다.멤브레인 내에서 규칙을 적용하는 방법은 다음과 같다.

  1. 규칙 입력에 멤브레인 내용에서 기호 할당
  2. 모든 입력이 충족되면 지정된 모든 기호를 막에서 제거하십시오.
  3. 모든 막에 대해 모든 규칙 할당이 이루어질 때까지 출력 기호를 작성하고 보류하십시오.
  4. 대상 막에 출력 기호를 추가하십시오.
  5. 필요에 따라 막 용해

출력물은 규칙 적용의 최대 병렬 특성을 위반할 수 있기 때문에 즉시 막으로 전달되지 않는다. 대신 가능한 모든 규칙이 적용된 후에 출력물이 분배된다.null

비결정적 응용

규칙 적용 순서는 무작위로 선택된다.규칙 적용 순서는 주어진 시간에 어떤 규칙을 적용할 수 있는지, 그리고 실행 단계의 결과에 상당한 영향을 미칠 수 있다.null

단 하나의 "a" 기호만 들어 있는 막을 생각해보면, 두 개의 법칙은 a → ab과 Δ이다.두 규칙 모두 "a" 기호가 존재하는데, 그 중 하나만 존재하기 때문에, 계산의 첫 번째 단계는 첫 번째 또는 두 번째 규칙 중 하나를 적용할 수 있지만 둘 다 적용될 수는 없을 것이다.이 단계의 가능한 두 가지 결과는 매우 다르다.

  1. 막은 "a" 기호와 "b" 기호가 모두 존재하는 계산의 다음 단계로 넘어가며, 다시 두 규칙 중 하나가 "a" 기호에 무작위로 할당된다.
  2. 막이 용해되고 하나의 "a" 기호가 포함된 막으로 전달된다.

최대 병렬 적용

이것은 모든 가능한 규칙 할당이 계산의 모든 단계에서 이루어져야 하는 규칙 어플리케이션의 속성이다.본질적으로 이것은 규칙 a → aa가 존재하는 "a" 기호가 발생할 때마다 규칙이 적용되기 때문에, 규칙 a → a는 단계마다 그것의 막에 있는 "a" 기호의 수를 두 배로 증가시키는 효과를 가지고 있다는 것을 의미한다.null

연산 모델로서

대부분의 P 시스템 변형은 계산적으로 보편적이다.[4]이것은 심지어 규칙 우선순위를 사용하지 않는 변종, 일반적으로 P 시스템의 근본적인 측면까지 포함한다.[6]null

계산 모델로서, P 시스템은 지수화 시간보다 짧은 시간에 NP 완성 문제를 해결할 수 있는 매력적인 가능성을 제공한다.[4]일부 P 시스템 변형은 SAT(부울 만족도) 문제를 선형 시간 내에[7] 해결할 수 있으며, 모든 NP-완전한 문제가 동등하기 때문에 이 기능은 그러한 모든 문제에 적용된다.그 자체로 P 시스템을 직접 구현하는 현재의 방법이 없기 때문에, 그 기능성은 대신[8] 에뮬레이션되고 따라서 NP-완전한 문제를 선형 시간 내에 해결하는 것은 이론적인 것으로 남아 있다.그러나 결정론적 P 시스템은 다항식 시간에 튜링 기계에서 시뮬레이션될 수 있다는 것도 입증되었다.[2]null

계산 예제

정사각형 숫자를 출력하는 P 시스템의 그래픽 표현

표시된 이미지는 3개의 막이 있는 P 시스템의 초기 상태를 묘사한다.P 시스템은 계층적 특성 때문에 종종 Venn 도표나 David Harel의 히그람(Statechart 참조)과 유사한 도면으로 그래픽으로 묘사된다.null

가장 바깥쪽 막인 1은 이 P계를 위한 용기 막이며 단일 아웃 규칙을 포함하고 있다.멤브레인 2는 여기서 4가지 규칙을 포함하며, 우선순위 관계에 있는 2가 c → c Δ보다 항상 우선하여 적용된다.델타 기호는 특별한 "disolve" 기호를 나타낸다.가장 안쪽의 막인 3은 여기에 타입의 기호("ac")와 세 가지 규칙을 포함하고 있다.이 초기 상태에서는 3막 이외의 규칙이 적용되지 않는다. 즉, 그 막 외부에 기호가 없다.그러나 시스템의 진화 과정에서 물체가 세포막 사이를 통과하면서 다른 세포막의 규칙이 활성화된다.null

연산

P 시스템의 비결정론적 특성 때문에 하나의 P 시스템이 할 수 있는 계산의 경로가 다양하여 다른 결과를 초래한다.다음은 표시된 P 시스템에 대한 가능한 계산 경로 중 하나이다.null

1단계

초기 구성에서 멤브레인 3에만 "ac"이라는 물체 함량이 있다.

  • "c"는 c → cc에 할당된다.
  • "a"는 a → ab에 할당된다.

2단계

막 3은 이제 다음을 포함한다: "abcc"

  • "a"는 → Δ에 할당된다.
  • "c"는 c → cc에 할당된다.
  • "c"는 c → cc에 할당된다.

한 단계 동안 동일한 규칙이 두 번 적용되도록 하는 규칙 응용 프로그램의 최대 병렬 동작에 주목하십시오.null

또한 첫 번째 규칙(a → ab)과 반대로 두 번째 규칙(a → bΔ)의 적용은 비결정적이며 무작위로 추정할 수 있다는 점에 유의하십시오.이 시스템은 첫 번째 규칙(그리고 동시에 c 입자를 두 배로 늘림)을 무한정 계속 적용하는 것과 마찬가지일 수 있다.null

이제 막 3은 용해된 기호(Δ)와 마주쳤고 이 막에서 나오는 모든 물체 함량이 막 2로 통과함에 따라 용해된다.null

3단계

막 2는 이제 다음을 포함한다: "bbcccc"

  • b → d에 "b"를 할당한다.
  • b → d에 "b"를 할당한다.
  • cc → c에 "ccc"
  • cc → c에 "ccc"

4단계

막 2에 "ddcc" 포함

  • "d"는 d → de에 할당된다.
  • "d"는 d → de에 할당된다.
  • cc → c에 "ccc"

5단계

막 2는 이제 다음을 포함한다: "dec"

  • "d"는 d → de에 할당된다.
  • "d"는 d → de에 할당된다.
  • "c"는 c → Δ에 할당된다.

c → Δ에 대한 우선 순위가 이제 해제되었으며 cc→c에 필요한 입력은 더 이상 존재하지 않는다.막 2는 이제 용해되고, 모든 물체 함량은 막 1로 전달된다.

6단계

멤브레인 1에 "디디" 포함

  • e → e에 "e"가out 할당됨
  • e → e에 "e"가out 할당됨
  • e → e에 "e"가out 할당됨
  • e → e에 "e"가out 할당됨

계산 중지

멤브레인 1은 "dd"를 포함하며, 아웃 규칙 e → e로out 인해 환경은 "eee"를 포함한다.이 시점에서는 규칙에 대한 개체의 추가 할당이 불가능하기 때문에 계산이 중단된다.계산 결과는 네 개의 "e" 기호가 있다.null

유일한 비결정론적 선택은 단독 "a" 기호를 지정할 위치를 선택할 때 1단계와 2단계 중에 일어났다.1단계에서 "a"를 → Δ에 할당하는 경우를 생각해 보십시오: 멤브레인 3에서 단 하나의 "b" 물체와 두 개의 "c" 물체가 용해되면 결국 하나의 "e" 물체만 생성되어 계산 결과로 전달될 수 있다.null

참고 항목

참조

  1. ^ Păun, Gheorghe (1998). Computing with Membranes. TUCS Report 208. Turku Centre for Computer Science. ISBN 978-952-12-0303-9. Retrieved 16 December 2012.
  2. ^ a b c d Păun, Gheorghe; Grzegorz Rozenberg (2002). "A guide to membrane computing". Theoretical Computer Science. 287 (1): 73–100. CiteSeerX 10.1.1.76.8425. doi:10.1016/S0304-3975(02)00136-6. ISSN 0304-3975.
  3. ^ Ardelean, Ioan; Matteo Cavaliere (June 2003). "Modelling biological processes by using a probabilistic p system software". Natural Computing. 2 (2): 173–197. doi:10.1023/A:1024943605864. ISSN 1567-7818.
  4. ^ a b c d e f Păun, Gheorghe (2006). "Introduction to Membrane Computing". Applications of Membrane Computing. Springer Berlin Heidelberg. pp. 1–42. ISBN 978-3-540-29937-0.
  5. ^ Nash, Anthony; Sara Kalvala (2019). "A P system model of swarming and aggregation in a Myxobacterial colony". Journal of Membrane Computing. 1: 103–11. doi:10.1007/s41965-019-00015-0.
  6. ^ Freund, Rudolf; Kari, Lila; Oswald, Marion; Sosík, Petr (2005). "Computationally universal P systems without priorities: two catalysts are sufficient". Theoretical Computer Science. 330 (2): 251–266. doi:10.1016/j.tcs.2004.06.029. ISSN 0304-3975.
  7. ^ Păun, Gheorghe (2001). "P systems with active membranes: attacking NP-complete problems" (PDF). Automata, Languages and Combinatorics. 6 (1): 75–90. Retrieved 2008-02-03.
  8. ^ Zandron, Claudio; Claudio Ferretti; Giancarlo Mauri (2000). "Solving NP-Complete Problems Using P Systems with Active Membranes". Unconventional Models of Computation. pp. 289–301. ISBN 1-85233-415-0.

외부 링크

  • P 시스템 – P 시스템 연구를 위한 웹 사이트.