내포어

Nested word

컴퓨터 과학에서, 특히 오토마타형식 언어 이론에서, 내포 단어는 Alur와 Madhusudan에 의해 제안된 개념으로, 전통적으로 선형 순서 구조를 모델링하는 데 사용되는 단어와 전통적으로 계층 구조를 모델링하는 데 사용되는 순서 없는 트리의 공동 일반화이다.중첩된 단어에 대한 유한 상태 수용자, 이른바 중첩된 단어 자동자는 단어에 대한 유한 자동의 보다 표현적인 일반화를 제공합니다.유한 중첩 단어 오토마타가 받아들이는 언어의 선형 인코딩은 눈에 보이는 푸시다운 언어의 클래스를 제공합니다.후자의 언어 클래스는 정규 언어결정론적 문맥이 없는 언어 사이에 적절히 놓여 있습니다.2004년 도입된 이래, 이러한 개념은 그 [1]분야에서 많은 연구를 불러일으켰다.

형식적 정의

중첩된 단어를 정의하려면 먼저 일치하는 관계를 정의합니다.음수가 아닌 { 의 경우 []{ [ \ell ]는{, , { 2, , \ \1, \특수대소문자 ] )을 나타냅니다

길이 0의 일치관계 {-},1, , - × {,, - ,θ, 2 \의 서브셋입니다.

  1. 모든 네스팅 에지는 전진한다., i µ j이면 i < j;
  2. 네스팅 엣지는 결코 유한한 위치를 공유하지 않는다. 즉, -disc < i < , , - - - - , that h h h - such , that such such such such such such such such such such h h such h h h nesting nesting nesting nesting nesting nesting nesting
  3. nesting edge는 교차하지 않습니다.즉, i < i > j < j >는 i and j와 i ′ j i j 모두 존재하지 않습니다.

포지션 i는

  • 포지션, ij에 대해 j를 구하면,
  • 보류중인 콜의 경우
  • 복귀 위치, 만약 h for i가 몇 시간 동안 유지된다면,
  • 보류 인 반환(-contract i i인 경우
  • 나머지 모든 사건에서 내부적 위치

알파벳 σ 위에 네스트된 {\ { \ell}은 (w, ) 。w { style \}의 단어 또는 문자열이며, is은 길이{\ { style \}의 일치 관계입니다.

중첩된 단어를 일반 단어로 인코딩

알파벳 { ,, ... , { \Sigma = \ { { 1} , _ , \ , a {} {\、 \ ( \ }{\ {\} the the the the over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over over = { \ Sigma _ Sigma =\ { \ {a로 표시된 중첩 단어에서 a로 표시된 반환 위치를 부호화하기 위한 기호 aθ, 마지막으로 a로 표시된 내부 위치를 나타내기 위한 기호 a 자체. 정확하게는 display 위의 중첩된 단어를위의 에 매핑하는 로서 각 중첩된 ( 1 _ {\ w _ { \ )가 x에 매핑되도록 합니다 }= i가 각각 콜 위치(보류 중), 내부 위치 및 반환 위치(보류 중)인 문자 {\}}는 a, a a입니다.

예를 들어, w=abaabcca와 일치 관계 = {(-baabca), (2,ba), (3,4), (5,7), (8,ba)}인 3진 알파벳 위에 n = (w,baabca)가 중첩된 단어라고 합니다.그 후, 워드로서의 부호화는 「(n)= a'b'aa'bcc'ca」라고 읽힙니다.

오토마타

중첩된 단어 자동화

내포된 단어 오토마톤은 유한한 수의 상태를 가지며 고전 문자열의 결정론적 유한 오토마톤과 거의 동일한 방식으로 동작한다: 고전적인 유한 오토마톤은 입력 w w { well {\ { displaystyle }}}}}를 왼쪽에서 오른쪽으로 읽고 j번째 문자를 읽은 후 오토마톤 상태를 읽는다. j{\}}는 w j { 전에 자동이 있었던 상태에 따라 달라집니다.

nested word automaton에서는 nested word(w,)) 내의 j{ j 반환 위치일 수 있습니다.그 경우 읽은 후의 상태는 j}를 전의 선형 상태에 따라 달라질 수 있습니다.대응하는 콜 위치에 있을 때 오토마톤에 의해 자극됩니다.단어의 규칙적인 언어와 유사하게, 내포된 단어의 집합 L은 어떤 (무한 상태) 내포된 단어 자동화에 의해 받아들여질 경우 규칙이라고 불립니다.

가시적인 푸시다운 자동화

중첩된 단어 오토마타는 중첩된 단어를 받아들이는 자동 모델입니다.(일반적인) 단어로 작동하는 동등한 오토마톤 모델이 있습니다.즉, 결정론적 푸시다운 자동화의 개념은 결정론적 푸시다운 자동화의 개념의 제한이다.

Alur와 Madhusudan에 [2]이어 결정론적 푸시다운 오토마톤은 공식적으로 M( Q , 、 0 、 , F) ( m= ( , { \ hat \ } , \ , \\ )로 정의된다.

  • Q 유한한 상태의 집합입니다.
  • ^ \ \ sigma}는 입력 으로 일반 푸시다운오토마타와 달리 \ \{ \ { c r \ style \ { \text{ r } \ text style \ \ _ tyl 。The alphabet denotes the set of call symbols, contains the return symbols, and the set contains the internal symbols,
  • is a finite set which is called the stack alphabet, containing a special symbol denoting the empty stack,
  • \displaystyle \=\ \{r \ _ 의 트랜지션, 리턴 트랜지션 및 내부 트랜지션에 대응하는 3개의 부분으로 분할되어 있습니다.
    • :Q × cQ × ( \ \ \ } \ \ { \ { } \ Q \times \ Gamma) 。
    • :Q × r × {\ { } \ \ { { r } \ \ \ Q}, 반환 전이 함수
    • Q \ _Q 내부 전이 함수,
  • 00}\ 초기 상태이며,
  • Q ( \ F \ )는 수용 상태의 집합입니다.

눈에 보이는 푸시다운 오토마톤의 계산 개념은 푸시다운 오토마타에 사용되는 오토마톤의 제한이다.푸시다운 오토마타는 콜 c{\ in _을 읽을 때만 스택에 심볼을 합니다 } \ 을(를) 읽습니다.수용 상태로 끝나는 계산은 수용 계산입니다.

그 결과, 눈에 보이는 푸시다운 오토마톤은 같은 입력 기호를 사용하여 스택을 푸시하거나 스택에서 팝할 수 없습니다.따라서 언어 { b a nn n N { L \ { \ n \mathrm \}은의 파티션에 대해 가시적인 푸시다운 오토마톤에 의해 받아들여질 수 없습니다만, 이 언어는 받아들여지고 있습니다.

부착 알파벳 위의L 결정론적 가시적 푸시다운 오토마톤에 의해 받아들여진 L({ L 가시적 푸시다운 언어라고 불립니다.

비확정적인 가시적인 푸시다운 오토마타

비결정론적 가시적 푸시다운 오토마타는 결정론적 오토마타만큼 표현적이다.따라서 비결정론적 푸시다운 오토마톤을 결정론적 오토마톤으로 변환할 수 있지만, 비결정론적 오토마톤이\ s 2 [3]가질 수 있다.

의사결정 문제

A의 설명 크기({A라고 , 시간O( 3 in)에서 단어 n이 오토마톤에 의해 받아들여지는지를 확인할 수 있습니다특히, O}\ell에서는, 공허 문제는 O로 해결할 수 있습니다. O^{ A A 고정된 O O O 결정됩니다 서 d(\ d 스트리밍 표시의 n 깊이입니다.O ( \ log ( \ell )) } time o ( \ style ( \ (\ ))시간 O ( \ ( \ )) displaydisplay o o o o o 、 、 o o o o o o o o o o o O ( \ \ log \ [2]

2개의 비결정적 오토마타 A, B에 대해 A에 의해 받아들여진 단어 세트가 B에 의해 받아들여진 단어의 서브셋인지 아닌지를 판단하는 것은 EXPTIME-complete이다.또한 EXPTIME-complete에서 [2]허용되지 않는 단어가 있는지 확인합니다.

언어들

가시적인 푸쉬다운 오토마타의 정의에서 알 수 있듯이 결정론적 푸쉬다운 오토마타는 결정론적 푸쉬다운 오토마타의 특수한 경우로 간주할 수 있습니다.따라서 에서의 가시적인 푸쉬다운 언어의 집합 VPL은 결정론적 컨텍스트프리 언어의 집합 DCFL의 서브셋을 형성합니다. { }, {\{\ 특히 중첩된 단어에서 일치 관계를 제거하는 기능은 중첩된 단어 위의 일반 언어를 컨텍스트 없는 언어로 변환합니다.

닫힘 속성

가시적인 [3]푸시다운 언어 세트는 다음 조작으로 닫힙니다.

  • set 조작:
    • 조합
    • 교차로
    • 보완,
따라서 부울 대수를 발생시킨다.

교차로 운영의 경우 간단한 제품 구조(Alur & Madhusudan 2004)로 2개의 M_{1 style M_{2})를 시뮬레이션한 VPA M을 구축할 수 있습니다.i , i의 경우 })는 ( ^, Fi { \된다고 가정합니다.다음으로 오토마톤M의 경우 상태 ×({}\2초기 상태는 ( 1,s 최종 상태 세트는 입니다. 초기 스택기호는(,입니다

을 읽을 때 M M 상태1, 2)인 M\ a심볼(\ M을 누른다displaystyle \ {{}, 여기서 상태 에서({displaystyle })로 이행할 때 })에 의해 푸시되는 스택 입니다displaystyle

내부 a M 읽을 때 M{{이 상태2})인 M{{M 로 전환될 마다 상태(q1,)로 바뀝니다.a를 읽을 때 {\ 에서합니다.

M{\ M) 상태, 2 반환 기호 a {\ 읽을 때 으로M {\ M(가 스택에서 심볼(\1},2 팝하여 상태 1,2)로 이행합니다}에 의해 팝됩니다. displaystyle })에서 })로 전환할 때 when를 읽습니다.} 를 클릭합니다.

상기 구성의 정확성은 시뮬레이션된 ({ M_}})과({display 2})의 푸시 및 팝 동작이 판독된 입력 기호를 따라 동기화된다는 사실에 달려 있습니다.사실, 결정론적 문맥 자유 언어의 더 큰 클래스가 더 이상 교차로 아래에서 닫히지 않기 때문에, 결정론적 푸시다운 오토마타에 대해 유사한 시뮬레이션이 더 이상 가능하지 않다.

위에서 나타낸 연결 구조와는 대조적으로, 눈에 보이는 푸시다운 자동화를 위한 보완 구조는 결정론적 푸시다운 자동화를 위한 표준 구조와[4] 유사하다.

또한 문맥 자유 언어의 클래스와 마찬가지로 가시적으로 푸시다운 언어의 클래스는 접두사 폐쇄 및 반전 에서 닫힙니다. 따라서 접미사 폐쇄도 마찬가지입니다.

다른 언어 수업과의 관계

Alur & Madhusudan(2004)은 눈에 보이는 푸시다운 언어가 McNaughton(1967)에서 제안된 괄호 언어보다 더 일반적이라고 지적한다.으로서 Crespi Reghizzi 및에 의해;Mandrioli(2012년), 차례로 눈에 띄게 푸시 다운 언어 엄격하게 언어 operator-precedence grammars에서 설명하는 플로이드가(1963년)고 같은 폐쇄 속성과 특성ω 언어와 논리와automata-based에( 보Lonati(알.(2015년)을 즐기도입되었었는지 의 클래스에 포함된 보여 주었다. 차문자화).콘텍스트 프리 문법의 일반화인 접속 문법과 비교하여 Okhotin(2011) target:은 선형 접속 언어가 눈에 띄게 푸시다운 언어의 슈퍼 클래스를 형성함을 보여준다.이 글의 말미에 있는 표는 촘스키 계층 내 다른 언어 패밀리와 관련하여 눈에 보이는 푸시다운 언어 패밀리를 나타내고 있습니다.라지예프 알루르와 파르타사라시 마두수단은[5][6] 일반 바이너리 트리 언어의 하위 클래스를 눈에 띄게 밀어내기 언어와 연관시켰다.

기타 설명 모델

눈에 보이는 푸시다운 문법

눈에 보이는 푸시다운 언어는 눈에 보이는 푸시다운 [2]문법으로 설명할 수 있는 언어입니다.

눈에 보이는 푸시다운 문법은 문맥이 없는 문법의 제한으로 정의할 수 있습니다.가시적인 푸시다운 문법 G는 4 태플에 의해 정의됩니다.

( 0 ,,) { G= ( \ V1} , \ 、 , , } 。여기서

  • 0 V 1({ V},})은 분리된 유한 집합이며, 각 v ({ vV})는 비말단 문자 또는 변수라고 불립니다.각 변수는 문장에서 다른 유형의 구 또는 절을 나타냅니다.각 변수는 G G에서 된 언어의 하위 언어를 정의합니다.V V 언어는 보류 중인 콜 또는 보류 중인 반환이 없는 언어입니다.
  • { \ Sigma}는 의 실제 내용을 구성하는 V {\ displaystyleV유한한 단말기 세트입니다.터미널 세트는 G(\ G에 의해 정의된 언어의 알파벳입니다.
  • R VV에서 (\cup \Sigma까지의 유한관계입니다이러한 값은 " () ) ):( , w )" \ \ , \문법의 산물개서 규칙에는 3종류가 있습니다. V 0( \ X , \ V , \ V { 0} 、 { \ a \\ { \ b \ \ }
    • (\ X) X 0 (\ XV^{0})이면Y 0 (\ V^{0}) [] (\ a\ Sigma
    • a b {\ X aZb Y} 、 X v V v 0 \ X V}이면 \ Y V
  • V ( \ S \ V)는 문장(또는 프로그램) 전체를 나타내기 위해 사용되는 시작 변수(또는 시작 기호)입니다.

여기서 아스타리스크는 Kleene 별 연산을 나타내고, {\{ 빈 단어입니다.

균일한 부울 회로

길이 { }이(가) 지정된 중첩 워드 오토마톤에 의해 허용되는지 여부는 깊이 O 균일한 부울 회로(\로 해결할 수 있습니다[2]

논리적인 설명

중첩된 단어에 대한 일반 언어는 2개의 단일 술어 콜과 리턴, 선형 후계자 및 일치 관계 '를 가진 모노디드 2차 로직으로 기술된 언어 세트입니다.[2]

「 」를 참조해 주세요.

메모들

  1. ^ Google Scholar 검색 결과에서 "nasted words" 또는 "visible pushdown"을 검색합니다.
  2. ^ a b c d e f g Alur & Madhusudan (2009)
  3. ^ a b Alur & Madhusudan (2004)
  4. ^ Hopcroft & Ullman(1979년, 페이지 238 f).
  5. ^ Alur, R.; Madhusudan, P. (2004). "Visibly pushdown languages" (PDF). Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04. pp. 202–211. doi:10.1145/1007352.1007390. ISBN 978-1581138528. S2CID 7473479. 제4장 정리 5
  6. ^ Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words" (PDF). Journal of the ACM. 56 (3): 1–43. CiteSeerX 10.1.1.145.9971. doi:10.1145/1516512.1516518. S2CID 768006. 제7장

레퍼런스

외부 링크