복잡함수

컴퓨터 과학에서 단어나 문자열의 복잡함수(일부 알파벳에서 기호의 유한 또는 무한 순서)는 그 문자열의 구별되는 요소(연속 기호의 하위 문자열)의 수를 세는 함수다.보다 일반적으로, 형식 언어의 복잡함수(유한 문자열의 집합)는 주어진 길이의 구별되는 단어의 수를 계산한다.

단어의 복잡성 함수

알파벳에서 기호의 순서가 되게 하라.양의 정수 n의 함수 p_u(n)를 문자열 u에서 n의 길이가 다른 요인(결합 하위 문자열)의 수로 정의한다.^{[1][2][3][4][5]}

k사이즈의 알파벳보다 적어도 n의 길이의 끈을 위해 우리는 분명히 가지고 있다.

${\displaystyle 1\leq p_{u}(n)\leq k^{n}\,}$

상수 단어와 불연속 단어,^[6][7] 예를 들어 각각 참퍼나운 단어들에 의해 달성되는 한계무한단어 u에 대해서는, u가 궁극적으로 주기적인 경우(아마도 비어 있을 수 있는 유한한, 빈 순서에 이어 유한한 사이클이 뒤따르는 경우) p_u(n)의 경계가 있다.반대로 p_u(n) ≤ n이 일부 n에 대해 존재한다면, u는 궁극적으로 주기적이다.^[3][8]

주기적인 순서는 궁극적으로 주기적이지 않은 것이다.주기적 시퀀스는 엄격히 복잡성 함수를 증가시킨다(이것은 Morse–이다).Hedlund 정리)^[9][10] 따라서 p(n)는 최소한 n+1이다.^[11]

길이 n의 각 부분집합_n S가 최대_n 두 개의 구별되는 값을 갖는 S 단어의 해밍 가중치를 갖는다면 유한 이항 단어의 집합 S는 균형을 이룬다.균형잡힌 순서는 요인 집합이 균형잡힌 순서 중 하나이다.^[12]균형잡힌 순서는 최대 n+1의 복잡함수를 가진다.^[13]

2진수 알파벳 위에 있는 스터미어 단어는 복잡함수 n + 1. ^[14]순서는 균형잡히고 주기적인 경우에만 스터미어다.^[2][15]그 예가 피보나치어다.^[14][16]보다 일반적으로 크기가 k인 알파벳보다 큰 스터미어 단어는 복잡성 n+k-1이다.3번째 알파벳 위에 있는 Arnoux-Rauzy 단어는 2n + 1의 복잡성을 가지고 있다:^[14] 예는 Trivonacci 단어 이다.^[17]

반복적인 단어의 경우, 각 요인이 무한히 자주 나타나는 단어의 경우, 복잡성 함수는 요인 집합을 거의 특징짓는다: s가 t와 동일한 복잡성 함수를 가진 반복 단어라면, Δ는 t 또는 Δt와 동일한 요인 집합을 가지며 여기서 Δ는 모폴리즘 a → aa를 두 배로 증가시키는 문자를 나타낸다.^[18]

언어의 복잡성 함수

L을 알파벳 위에 있는 언어가 되게 하고, L에서^[9] 길이 n의 다른 단어의 수로 양의 정수 n의 함수 p_L(n)를 정의한다. 단어의 복잡함수는 따라서 그 단어의 인자로 구성된 언어의 복잡함수다.

언어의 복잡함수는 단어의 복잡함수보다 제약이 적다.예를 들어, 경계는 될 수 있지만 결국 일정하지는 않다: 정규 언어 $a{\displaystyle }$( ${\displaystyle b{}^{}}$) $∗{\displaystyle a(bb)^{*}a}$의 복잡함수는 각각 홀수와 짝수 n n2에 대한 값 3과 4를 취한다$$.모스-모스-의 아날로그가 있다.Hedlund 정리: L의 복잡성이 일부 n에 대해 p_L(n) n n을 만족한다면 p는_L 경계되고 다음과 같은^[9] 유한한 언어 F가 있다.

${\displaystyle L\subseteq \{xy^}z:x,y,z\in F,\k\in \mathb {N}\}\in.$

다항식 또는 희박한 언어는 복잡함수 p(n)가 n의 고정된 힘에 의해 경계되는 언어다.다항식이 아닌 정규어는 지수적이다: 일부 고정 k > 1의 경우 p(n)가 k보다ⁿ 큰 n이 무한히 많다.^[19]

관련개념

무한 시퀀스 u의 위상 엔트로피는 다음에 의해 정의된다.

${\displaystyle H_{\mathrm {top} }=\lim _{n\rightarrow \inflt }{\frac {\log p_{u}(n){n\log k}\ .}$

복잡성 함수의 로그가 하위 부가성이기 때문에 한계가 존재한다.^[20][21]0과 1 사이의 모든 실제 숫자는 일부 시퀀스의 위상학적 엔트로피가 적용 가능한 것으로서 발생하며,^[22] 이 엔트로피는 균일하게 반복되거나^[23] 심지어 고유하게 에고다이컬한 것으로 간주될 수 있다.^[24]

x 실수와 b 정수 ≥ 2의 경우 base b에서 x의 복잡도 함수는 base b에서 x의 자릿수 순서의 복잡도 함수 p(x,b,n)이다.x가 비합리적인 숫자라면 p(x,b,n) ≥ n+1을, x가 합리적이면 p(x,b,n) ≤ C를 x와 b에 따라 일정하게 C를 구한다.^[6]대수적 비합리적 x의 경우 복잡성은 b(그런ⁿ 숫자가 모두 정상이면 뒤따를 것)라고 추측하지만, 이 경우에 알려진 모든 것은 p가 n의 어떤 선형 함수보다 빠르게 성장한다는 것이다.^[25]

아벨의 복잡성 함수 p^ab(n)는 주어진 길이 n의 구별되는 인자의 발생 횟수를 비슷하게 계수하며, 여기서 우리는 위치의 순열화에 의해서만 다른 인자를 식별한다.분명히 p^ab(n) ≤ p(n)이다.스터미아 수열의 아벨의 복잡성은 p^ab(n) = 2를 만족한다.^[26]

참조

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl 1260.11001.
• Cassaigne, Julien; Nicolas, François (2010). "Factor complexity". In Berthé, Valérie; Rigo, Michel (eds.). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. pp. 163–247. ISBN 978-0-521-51597-9. Zbl 1216.68204.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
• Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.