단어 조합

이 글은 수학이나 컴퓨터 과학의 전문가의 주의가 필요하다.구체적인 문제는 리바이스 보조정리, 파인 앤드 윌프의 정리, 마카닌의 알고리즘 등 자유 모노이드에서 핵심 결과를 놓친다는 점이다. 위키프로젝트 수학 또는 위키프로젝트 컴퓨터 과학이 전문가 영입에 도움이 될 수 있다. (2015년 2월)

단어에 대한 콤비네이터틱스는 단어와 형식 언어의 연구에 초점을 맞춘 콤비네이터틱스로부터 분기되는 상당히 새로운 수학 분야다.주제는 문자나 기호, 그리고 그것들이 형성하는 순서를 살펴본다.단어에 대한 결합학은 대수학과 컴퓨터 과학을 포함한 수학 연구의 다양한 분야에 영향을 미친다.그 분야에 대한 기여는 매우 광범위했다.첫 작품 중 일부는 1900년대 초 악셀 투에 의해 사각형이 없는 단어로 쓰여졌다.그와 동료들은 단어 안에 있는 패턴을 관찰하고 설명하려고 노력했다.시간이 흐르면서 단어에 대한 콤비네이터학은 알고리즘과 코딩 연구에 유용하게 쓰이게 되었다.추상 대수학의 발달과 개방형 질문에 대한 답으로 이어졌다.

정의

결합학은 이산 수학의 한 분야다.이산 수학은 셀 수 있는 구조를 연구하는 학문이다.이 물건들은 출발과 끝이 확실하다.열거할 수 있는 대상에 대한 연구는 미적분학과 무한 구조를 연구하는 분석과 같은 학문과는 정반대다.조합학에서는 다양한 표현을 사용하여 이러한 개체를 계산하는 방법을 연구한다.단어에 대한 콤비네이터틱스는 단어와 격식어 연구에 초점을 맞춘 이 분야의 최근 발전이다.공식 언어는 사람들이 정보를 전달하기 위해 사용하는 기호와 기호의 조합의 모든 집합이다.^[1]

단어 연구와 관련된 일부 용어가 먼저 설명되어야 한다.첫째로, 무엇보다도, 단어는 기본적으로 유한 집합의 기호, 또는 문자의 배열이다.^[1]이 세트들 중 하나는 일반 대중들에 의해 알파벳으로 알려져 있다.예를 들어, "encyclopedia"라는 단어는 영어 알파벳의 기호들의 배열로, 26자로 구성된 유한 집합이다.한 단어를 수열로 설명할 수 있기 때문에, 다른 기본적인 수학적 설명이 적용될 수 있다.알파벳은 집합이므로, 예상한 대로, 빈 집합은 부분 집합이다.즉, 길이 0이라는 독특한 단어가 존재한다.낱말의 길이는 순서를 구성하는 기호의 수로 정의되며, 백과사전은 12개의 글자를 가지고 있기 때문에 w = 12라는 예시를 다시 보면 w.^[1]큰 숫자를 인수한다는 생각은 단어에 적용될 수 있는데, 여기서 단어의 요인은 연속된 기호의 블록이다.^[1]따라서, "사이클로프"는 "엔시클로페디아"의 한 요소다.

그 자체로 시퀀스를 검토하는 것 외에도, 단어들에 대한 조합학을 고려해야 할 또 다른 영역은 그것들이 어떻게 시각적으로 표현될 수 있는가이다.수학에서는 데이터를 인코딩하는 데 다양한 구조가 사용된다.조합에 사용되는 일반적인 구조는 나무 구조다.트리 구조(tree structure)는 하나의 선으로 정점이 연결되는 그래프를 말하며, 이를 경로나 에지라고 한다.나무에는 주기가 포함될 수 없으며, 완전하거나 완전하지 않을 수도 있다.단어는 기호에 의해 구성되기 때문에 단어를 인코딩하고, 트리를 사용하여 데이터를 인코딩하는 것이 가능하다.^[1]이것은 물체의 시각적 표현을 제공한다.

주요기부금

주제의 기원을 요약한 단어에 대한 결합학에 대한 첫 번째 책들은 M. 로트하이어라는 이름으로 통째로 간 수학자들 그룹에 의해 쓰여졌다.그들의 첫 번째 책은 단어에 대한 콤비네이터가 더 널리 보급된 1983년에 출판되었다.^[1]

패턴

단어 내 패턴

단어 콤비네이터의 발달에 기여한 주역은 악셀 투에(1863–1922)이다. 그는 반복을 연구했다.Thue의 주된 공헌은 무한정 네모 없는 말의 존재에 대한 증거였다.사각형이 없는 단어에는 인접한 반복 요소가 없다.^[1]명확히 하자면, m은 연속해서 반복되기 때문에 "여름"은 사각형이 아닌 반면, "enclopedia"는 사각형이 없는 것이다.Tue는 대체물을 사용함으로써 무한정 사각형이 없는 단어의 존재에 대한 그의 추측을 증명한다.치환이란 기호를 취하여 단어로 대체하는 방법이다.그는 이 기술을 자신의 다른 공헌인 Thue-Morse 시퀀스 또는 Thue-Morse 단어를 묘사하기 위해 사용한다.^[1]

투에는 네모 없는 단어에 대해 두 개의 논문을 썼는데, 그 중 두 번째는 투-모스 단어에 있었다.마스턴 모스는 투와 같은 결과를 발견했지만 그들은 독립적으로 일했기 때문에 그 이름에 포함된다.투에 역시 중복되지 않는 단어의 존재를 증명했다.겹치지 않는 단어는 두 기호 x와 y의 경우 패턴 xyxx가 단어 내에 존재하지 않는 경우를 말한다.그는 두 번째 논문에서 무한 중복 없는 단어와 네모 없는 단어 사이의 관계를 증명하기 위해 계속한다.그는 서로 다른 두 글자를 사용하여 만든 겹치지 않는 단어를 취하며, 치환법을 사용하여 세 글자의 사각 없는 단어로 어떻게 변형될 수 있는지를 보여준다.^[1]

앞에서 기술한 바와 같이, 단어들은 기호에 의해 만들어진 순서를 조사함으로써 연구된다.패턴이 발견되고, 수학적으로 묘사될 수 있다.패턴은 피할 수 있는 패턴이거나 피할 수 없는 패턴일 수 있다.피할 수 없는 패턴, 즉 규칙성의 작업에 중요한 기여자는 1930년 프랭크 램지였다.그의 중요한 정리는 정수 k, m³2의 경우 최소 양의 정수 R(k,m)이 존재하여 완전한 그래프를 두 가지 색으로 채색하는 방법에도 불구하고, 각 색상의 솔리드 컬러 하위 그래프가 항상 존재하게 된다는 것이다.^[1]

피할 수 없는 패턴의 연구에 다른 기여자들로는 반 데어 웨르덴이 있다.그의 정리는 만약 양의 정수를 k 등급으로 나누면, c 등급이 어떤 알려지지 않은 길이의 산술적 추이를 포함하는 등급 c가 존재한다고 말한다.산술적 수열은 인접한 수 사이의 차이가 일정하게 유지되는 수열이다.^[1]

피할 수 없는 패턴을 조사할 때는 육각류도 연구한다.일부 패턴 x,y,z의 경우, sesquipower는 x, xyx, xyxxx, ....이것은 사각형이 없는, 또는 피할 수 없는 패턴과 같은 또 다른 패턴이다.쿠드랭과 슈트젠베르거는 주로 집단 이론 응용을 위해 이 세스키포우어를 연구했다.게다가, 지민은 세시포워들이 모두 피할 수 없다는 것을 증명했다.전체 패턴이 나타나든, 아니면 세시파워의 일부 조각만 반복적으로 나타나든, 그것을 피할 수는 없다.^[1]

알파벳 내의 패턴

목걸이는 원형 순서의 단어들로 구성된다.그것들은 음악과 천문학에서 가장 자주 사용된다.1894년에 Flye Sainte-Marie는 길이 2의ⁿ 바이너리 de Bruijn 목걸이가 있다는²ⁿ⁻¹⁻ⁿ 것을 증명했다.드 브루윈 목걸이에는 일정 수의 글자 위에 길이 n의 단어로 만들어진 요소가 포함되어 있다.그 말은 목걸이에 단 한 번만 나타난다.^[1]

1874년 바우도는 바이너리 데 브루옌 목걸이 이론을 적용해 결국 모스 부호를 대신할 코드를 개발했다.문제는 1934년 사인테 마리부터 마틴까지 이어졌는데, 마틴은 드 브뤼옌 구조의 말을 만드는 알고리즘을 살펴보기 시작했다.그 후 1943년 사후에 의해 작업되었다.^[1]

언어 계층

단어들의 조합에 가장 많이 적용된 결과는 아마도 Noam Chompsky에 의해 개발된 Chompsky 계층 구조일 것이다.그는 1950년대에 공식적인 언어를 공부했다.^[2]그의 언어관습은 주제를 단순화시켰다.그는 단어의 실제 의미를 무시하고, 빈도나 맥락과 같은 특정 요소를 고려하지 않으며, 모든 길이에 단어의 패턴을 적용한다.촘스키 작품의 기본 개념은 언어를 네 가지 수준, 즉 언어 서열로 나누는 것이다.네 가지 수준은 규칙적이고, 문맥이 없고, 문맥에 민감하며, 계산적으로 열거할 수 있거나 제한되지 않는다.^[2]규칙적인 것이 가장 덜 복잡한 반면 계산적으로 셀 수 없이 많은 것이 가장 복잡하다.그의 연구는 단어에 대한 결합론에서 발전했지만, 그것은 다른 학문, 특히 컴퓨터 과학에 큰 영향을 미쳤다.^[3]

단어 유형

스터미어

프랑수아 스투름에 의해 만들어진 스터미언어는 단어에 대한 콤비네이터릭에 뿌리를 두고 있다.스터미어 단어에는 몇 가지 동등한 정의가 존재한다.예를 들어 무한 단어는 모든 음이 아닌 정수 n에 대해 길이 n의 n+1 고유 인자를 갖는 경우에만 스터미언이다.^[1]

린든어

린든 워드는 주어진 알파벳 위에 쓰여진 단어로서, 각각의 결합 클래스 중에서 가장 단순하고 가장 순서가 높은 형태로 쓰여진다.린든 워드는 중요한데 어떤 린든 워드 x에 대해서도 y<z, x=yz와 함께 y와 z가 있기 때문이다.나아가 어떤 단어도 린다온어의 고유한 요소화를 가지고 있다고 하는 첸, 폭스, 린든의 정리도 존재하는데, 여기서 요소화 단어들은 비증가한다.이러한 특성 때문에 린다온어는 대수학, 특히 집단 이론을 연구하는 데 사용된다.그들은 정류자 사상의 기초를 이룬다.^[1]

시각적 표현

코브햄은 유한한 오토마타(Augene Prouette)와 관련된 연구를 기고했다.수학 그래프는 가장자리와 노드로 만들어진다.유한한 자동자(automata)를 사용하여 가장자리에는 알파벳 문자로 라벨이 표시된다.그래프를 사용하려면, 한 노드에서 시작하여 가장자리를 따라 이동하여 최종 노드에 도달한다.그래프를 따라 이동한 경로가 단어를 형성한다.노드와 가장자리 수가 셀 수 있고, 하나의 경로만이 두 개의 구별되는 노드를 연결하기 때문에 유한 그래프다.^[1]

1838년 칼 프리드리히 가우스(Carl Friedrich Gauss)가 만든 가우스 코드는 그래프에서 개발된다.구체적으로는 평면의 닫힌 곡선이 필요하다.곡선이 한정된 횟수로만 교차할 경우, 교차로에 사용된 알파벳의 문자로 레이블을 지정한다.곡선을 따라 이동하면 교차점이 지나갈 때 글자 하나하나를 기록함으로써 단어가 결정된다.가우스는 같은 기호가 단어로 나타날 때의 거리가 짝수라는 것을 알아챘다.^[1]

집단 이론

발터 프란츠 안톤 폰 다이크는 1882년과 1883년에 출판된 그의 작품에 의해 집단 이론의 단어에 대한 콤비네이터의 작업을 시작했다.그는 말을 집단적 요소로 사용하는 것으로 시작했다.라그랑주 또한 1771년에 순열 그룹에 대한 연구로 기여했다.^[1]

집단 이론에서 연구된 단어들에 대한 조합론의 한 측면은 단어 감소다.그룹은 알파벳에서 일부 a에 대해 aa 또는 aa 형식의 인자를 제외하고 생성자와 역원소를 포함한 일부 알파벳에 단어들로 구성된다.감소된 단어들은 고유한 단어에 도달할 때까지 요소들을 취소하기 위해 aa, aa 인자를 사용할 때 형성된다.^[1]

닐슨 변형도 개발되었다.자유 집단의 요소 집합에 대해, 닐슨 변환은 세 가지 변환에 의해 달성된다. 즉, 요소를 그 반대로 대체하고, 원소를 그 자체와 다른 원소의 산물로 대체하며, 1과 동일한 원소를 제거한다.이러한 변형을 적용함으로써 Nielsen 감소된 세트가 형성된다.감소된 집합은 어떤 요소도 완전히 취소하기 위해 다른 요소와 곱할 수 없음을 의미한다.닐슨 변형과 스터미언어와의 연관성도 있다.^[1]

고려된 문제

집단 이론에서 단어에 대한 결합론 연구에서 고려된 한 가지 문제는 다음과 같다: 두 요소인 sem그룹 x에 대해 x와 y의 정의 관계를 x=y modulo로 한다.포스트와 마르코프는 이 문제를 연구했고 그것을 이해할 수 없다고 판단했다.해석할 수 없는 것은 그 이론이 증명될 수 없다는 것을 의미한다.^[1]

번사이드 문제는 무한 큐브 없는 단어의 존재를 사용하여 증명되었다.이 질문은 집단이 한정된 수의 발전기를 가지고 있고 집단의 x에 대한 기준ⁿ x=1을 충족하는지 묻는다.^[1]

포스트 서신 문제에 근거해 많은 단어 문제가 불분명하다.공통 도메인과 ${\displaystyle \mathrm{공통}}$ 코도메인을 가진$$ 어떤 두 개의 $동형문자{\displaystyle }$ g${\displaystyle ,}$ h ${\displaystyle$ g$,h}$은(는) ${\displaystyle g}$(${\displaystyle }$)${\displaystyle }$= ${\displaystyle h}$(${\displaystyle }$) ${\displaystyle g(w)=h(w)}$와 같은 $단어$가 도메인 내에$$ 존재하는지 여부를 묻는 포스트 통신 문제의 한 예를 형성한다$.$ 포스트는 이 문제가 불분명하다는 것을 증명했다; conseq.분명히, 이 기본적인 문제로 축소될 수 있는 어떤 단어 문제도 마찬가지로 이해할 수 없는 것이다.^[1]

기타 응용 프로그램

단어의 조합법은 방정식에 응용된다.마카닌은 방정식이 말로 구성될 때 유한한 방정식의 해답을 찾는 것이 가능하다는 것을 증명했다.^[1]

참고 항목

• 피보나치어
• 콜라코스키 수열
• 리바이스 보조정리
• 부분어
• 시프트 스페이스
• 워드 메트릭
• 워드 문제(컴퓨팅 능력)
• 단어 문제(수학)
• 그룹에 대한 단어 문제
• 영-피보나치 격자

참조

추가 읽기

외부 링크

위키미디어 커먼즈에는 콤비네이터릭스와 관련된 미디어가 단어 위에 있다.

• 장 베르스텔의 페이지
• 테로하쥬의 페이지
• 가이 멜랑손 페이지