항성 높이 문제

이 글은 인라인 인용문을 포함하지만 형식이 제대로 되어 있지 않다. 이 기사를 수정하여 개선하십시오. 괄호 참조는 더 이상 사용되지 않으며, 짧은 각주로 변환한다.(2020년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

공식 언어 이론의 항성 높이 문제는 모든 정규 언어가 제한된 항성 높이의 정규 표현, 즉 클레네 별의 둥지 깊이가 제한적인 표현을 사용하여 표현될 수 있는지에 대한 문제다.특히, 둥지 깊이는 항상 충분한가?그렇지 않다면 필요한 개수를 결정하는 알고리즘이 있는가?문제는 에그간(1963년)이 제기했다.

항성 높이에 제한이 없는 정규 언어의 패밀리

첫 번째 문제는 1963년 에그간이 n마다 항성 높이 n의 정규 언어의 예를 제시했을 때 부정적으로 답변되었다.여기서 일반 언어 L의 항성 높이 h(L)는 L을 나타내는 모든 정규식 중 최소 항성 높이로 정의된다.Eggan(1963)에 의해 발견된 처음 몇 개의 언어는 각 언어에 대해 규칙적인 표현을 하는 방법으로 다음과 같이 기술된다.

${\displaystyle {\requiredat}{2}e_{1}&=a_{1}^{*}\\\e_{2}=\left(a_{1}^{1}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*a_{2}^{*a_{3}\오른쪽)^{*}\왼쪽(a_{4}^{*a_{5}^{*}a_{6}\오른쪽)^{*}a_{7}\오른쪽)^{*}\\e_{4}&=\왼쪽(\왼쪽(a_{1}^{*a_{2}^{*a_{3}\오른쪽)^{*}\왼쪽(a_{4}^{*a_{5}^{*}a_{6}\오른쪽)^{*}a_{7}\오른쪽)^{*}\left(\왼쪽(a_{8}^{*a_{9}^{*a_{10}\오른쪽)^{*}\왼쪽(a_{11}^{*a_{12}^{*}a_{13}\오른쪽)^{*}a_{14}\오른쪽)^{*}a_{15}\오른쪽)^{*}\end{aignatedat}}}$

이러한 표현에 대한 구성 원리는 ${\displaystyle {en}_{}}$${\displaystyle {}_{}}$+ 1 ${\$$displaystyle e_{n+$$1}$의 두 사본을 연결한 다음$,$ 신선한 알파벳 기호를 사용하여 두 번째 복사본의 문자 이름을 적절하게 변경하고, 결과를 다른 새 알파벳 기호로 연결한 다음 다음을 통해 식을 얻는 것이다$$.클레인 스타로 결과표현을 감싸고 있다.나머지, 더 어려운 부분은 ${\displaystyle {en}_{}}$ ${\$에 대해 n보다 작은 항성 높이의 등가 정규 표현은 없다는$$ 것을 증명하는 것이다. (Eggan 1963)에 증거가 제시되어 있다.

그러나 Eggan의 예는 항성 높이 n을 가진 언어의 경우 크기가 2-1인ⁿ 큰 알파벳을 사용한다.그래서 그는 우리가 이항 알파벳을 통해서도 예를 찾을 수 있는지 물었다.이는 데장&슈첸베르거(1966년)에 의해 얼마 지나지 않아 사실로 증명되었다.이들의 예는 다음과 같이$$ 이진 문자 { a${\displaystyle }$,${\displaystyle b}$ ${\displaystyle \}}$ ${\displaystyle \{a,b\}}$에 걸쳐 귀납적으로 정의된 정규식 계열로 설명할 수 있다.Salomaa(1981):

${\displaystyle {\requiredat}{2}e_{1}&=(ab)^{*}\e_{2}&=\left(a(ab)^{*}bb(ab)^{*}\오른쪽)^{*}\\e_{3}&=\왼쪽(aa\left(aa)(ab)^{*}bb(ab)^{*}\오른쪽)^{*}bbb\왼쪽(aa(ab)ab)^{*}bb(ab)^{*}\오른쪽)^{*}\오른쪽)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}}$

다시 말하지만 ${\displaystyle {en}_{}}$ ${\$이(가) 항성 높이의 등가 정규식을 인정하지 않는다는$$ 사실에 대해서는 엄격한 증거가 필요하다.증거는 (Dejean & Schützenberger 1966)과 (Salomaa 1981)에 의해 주어진다.

정규 언어의 별 높이 계산

이와는 대조적으로, 두 번째 문제는 훨씬 더 어려운 것으로 판명되었고, 이 문제는 20년 이상 동안 공식적인 언어 이론에서 유명한 공개 문제가 되었다(브르조조프스키 1980).몇 년 동안 진전은 거의 없었다.순수 그룹 언어는 항성 높이 문제가 해독 가능한 것으로 입증된 최초의 일반 언어의 흥미로운 계열이었다(McNaughton 1967).그러나 이 일반적인 문제는 하시구치씨에 의해 해결되기 전까지 25년 이상 개방되어 있었는데, 하시구치씨는 1988년에 어떤 정규 언어의 별 높이를 결정하는 알고리즘을 발표하였다.알고리즘은 전혀 실용적이지 않았고, 비원소적 복잡성이었다.이 알고리즘의 막대한 자원 소비를 설명하기 위해 롬바르디와 사카로비치(2002)는 다음과 같은 실제 수치를 제공한다.

[하시구치씨가 기술한 절차]는 아주 작은 예라도 훨씬 불가능한 연산으로 이어진다.예를 들어, 루프 복잡성 3의 4개 상태 자동화에 의해 L이 수용되는 경우($그리고$ 작은 10개 요소 전환 단노이드 포함), 동등성을 위해 L로 시험할 언어 수의 매우 낮은 부차수는 다음과 같다$:{\displaystyle {}^{}}$ ( ${\displaystyle {{{10}^{}}^{}}^{}}$ ${\displaystyle {{10}^{}}^{{}^{}}}$) ( ${\displaystyle {{{{10}^{}}^{}}^{}}^{}}$ 10${\displaystyle {{{{}^{}}^{}{{10}^{}}^{}}^{}}^{}}$ )${\displaystyle {{}^{}}^{}}$( ${\displaystyle {{{{10}^{}}^{}}^{}}^{}}$ 10 ${\displaystyle {{{{10}^{}}^{}}^{}}^{}}$ ) ( ${\displaystyle {{{10}^{}}^{}}^{}}$ 10 10 ${\displaystyle {{{{}^{}}^{}}^{}}^{}}$. . ${\displaystystyle \(10^{$10^{10$}}}}}}}}\rig)^{\)^{\\\\\\\\\\\\\\\\\luth)$${10^{10}}}\오른쪽)^{\왼쪽(10^{10^{10}}\오른쪽)}}.$$}$

— S. Lombardy and J. Sakarovitch, Star Height of Reversible Languages and Universal Automata, LATIN 2002

${\displaystyle {\mathrm{숫자}}^{}}$만 ${\displaystyle {{\mathrm{보더라도}}^{}}^{}}$ 10$$10 $10$ {\$displaystyle 10^{10^{$10}}}은 소수 표기법으로 적을 때 100억 개의 0을 가지며$$, 이미 관측 가능한 우주의 원자 수보다 훨씬 많다.

하시구치의 절차보다 훨씬 효율적인 알고리즘은 2005년 커스틴에 의해 고안되었다.이 알고리즘은 입력으로 지정된 비결정적 유한 자동화에 대해 이중 외주 공간 내에서 실행된다.그러나 이 알고리즘의 자원 요구사항은 여전히 실현 가능하다고 간주되는 것의 여백을 크게 초과한다.

이 알고리즘은 콜콤베트와 뢰딩에 의해 2008년(콜콤베트 & 뢰딩 2008) 정규 비용함수 이론의 일환으로 나무로 최적화되고 일반화되었다.툴 스위트 스테미너에서 2017년 시행됐다.^[1]

참고 항목

• 일반화된 항성 높이 문제
• Kleene의 알고리즘 — 결정론적 유한 자동화에 의해 주어진 언어에 대한 정규식(일반적으로 최소 항성 높이)을 계산한다.

참조

인용된 작품

• Brzozowski, Janusz A. (1980). "Open problems about regular languages". In Book, Ronald V. (ed.). Formal language theory—Perspectives and open problems. New York: Academic Press. pp. 23–47. ISBN 978-0-12-115350-2. (기술 보고서 버전)
• Colcombet, Thomas; Löding, Christof (2008). "The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem". CSL. Lecture Notes in Computer Science. 5213: 416–430. doi:10.1007/978-3-540-87531-4_30. ISBN 978-3-540-87530-7. ISSN 0302-9743.
• Dejean, Françoise; Schützenberger, Marcel-Paul (1966). "On a Question of Eggan". Information and Control. 9 (1): 23–25. doi:10.1016/S0019-9958(66)90083-0.
• Eggan, Lawrence C. (1963). "Transition graphs and the star-height of regular events". Michigan Mathematical Journal. 10 (4): 385–397. doi:10.1307/mmj/1028998975. Zbl 0173.01504.
• McNaughton, Robert (1967). "The Loop Complexity of Pure-Group Events". Information and Control. 11 (1–2): 167–176. doi:10.1016/S0019-9958(67)90481-0.
• Salomaa, Arto (1981). Jewels of Formal Language Theory. Melbourne: Pitman Publishing. ISBN 978-0-273-08522-5. Zbl 0487.68063.

추가 읽기

• Hashiguchi, Kosaburo (1982). "Regular languages of star height one". Information and Control. 53 (2): 199–210. doi:10.1016/S0019-9958(82)91028-2.
• Hashiguchi, Kosaburo (1988). "Algorithms for Determining Relative Star Height and Star Height". Information and Computation. 78 (2): 124–169. doi:10.1016/0890-5401(88)90033-8.
• Lombardy, Sylvain; Sakarovitch, Jacques (2002). "Star Height of Reversible Languages and Universal Automata" (PDF). 5th Latin American Symposium on Theoretical Informatics (LATIN) 2002, Vol. 2286 of LNCS. Springer.
• Kirsten, Daniel (2005). "Distance Desert Automata and the Star Height Problem". RAIRO - Informatique Théorique et Applications. 39 (3): 455–509. doi:10.1051/ita:2005027.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.