단어 분리 문제

Separating words problem
컴퓨터 과학에서 해결되지 않은 문제:

두 개의 주어진 길이 n 문자열에서 다르게 동작하는 결정론적 유한 오토마톤에는 몇 개의 상태가 필요한가?

(컴퓨터 사이언스의 미해결 문제 증가)

이론 컴퓨터 과학에서, 분리 단어 문제는 주어진 두 문자열에서 다르게 동작하는 가장 작은 결정론적 유한 오토마톤을 찾는 문제이며, 이는 두 문자열 중 하나를 받아들이고 다른 문자열을 거부하는 것을 의미합니다.최악의 경우 입력 문자열 길이의 함수로서 이러한 자동화가 얼마나 커야 하는지는 미해결 문제입니다.

예

2개의 스트링 0010과 1000은 시작 상태에서2개의 다른 상태로 이행하는 3개의 스테이트 오토마톤에 의해 서로 구별될 수 있습니다.이러한 2개의 스테이트로부터의 후속의 이행은 항상 같은 스테이트로 돌아옵니다.이 자동의 상태는 입력 문자열의 첫 번째 기호를 기록합니다.2개의 터미널 상태 중 한쪽이 수용 중이고 다른 한쪽이 거부 중이면 자동은 0010과 1000 중 하나의 문자열만 수용합니다.단,[1] 이들 2개의 문자열은 상태가3개 미만인 오토마톤에서는 구별할 수 없습니다.

전제 조건의 단순화

이 문제에 대한 경계를 증명하기 위해 일반성을 잃지 않고 입력이 2글자 알파벳 위의 문자열이라고 가정할 수 있습니다.큰 알파벳 위의 두 문자열이 다른 경우 동일한 길이의 이진 문자열에 매핑하는 문자열 동형성이 존재합니다.바이너리 스트링을 구별하는 오토마톤은 상태 [1]수를 증가시키지 않고 원래 스트링을 구별하는 오토마톤으로 변환할 수 있습니다.

또한 두 문자열의 길이가 같다고 가정할 수도 있습니다.길이가 동일하지 않은 문자열의 경우 값이 2개의 입력 길이 중 작은 쪽의 소수 p가 항상 존재하기 때문에 2개의 길이가 서로 다른 모듈로 p입니다.이 경우 입력 모듈로p의 길이를 카운트하는 오토마톤을 사용하여 2개의 스트링을 서로 구별할 수 있습니다.따라서 길이가 일정하지 않은 [1]문자열은 상태가 거의 없는 오토마타에 의해 항상 서로 구별할 수 있습니다.

역사와 경계

주어진 두 개의 문자열을 구별하는 오토마톤의 크기를 제한하는 문제는 고랄치크 & 쿠벡(1986)에 의해 처음 공식화되었는데, 그는 오토마톤의 크기가 항상 [2]준선형임을 보여주었다.나중에 Robson(1989)은 [3]필요할 수 있는 자동 크기에 대해 알려진 최선의 상한인 O(n2/5(log n)3/5를 증명했다.이것은 Chase(2020)에 의해 O(n1/3(log n)7[4]로 개선되었습니다.

입력 쌍은 모두 길이 n의 바이너리 문자열이며 입력을 구별하는 오토마톤은 크기 δ(log n)를 가져야 합니다.이 하한과 롭슨 상한 사이의 격차를 좁히는 [1]것은 여전히 해결되지 않은 문제입니다.Jeffrey Shallit은 Robson의 [5]상한선을 개선하는 것에 대해 100 영국 파운드의 상금을 내걸었다.

특수한 경우

단어 분리 문제의 몇 가지 특수한 경우는 몇 가지 상태를 사용하여 해결할 수 있는 것으로 알려져 있습니다.

  • 두 이진어가 0 또는 1의 서로 다른 수를 갖는 경우, 해밍 가중치 모듈로를 로그 크기의 소수로 계산하여 서로 구별할 수 있습니다.보다 일반적으로 길이 k의 패턴이 두 단어에서 다른 횟수로 나타나는 경우 O([1]k log n) 상태를 사용하여 서로 구별할 수 있습니다.
  • 두 개의 이진어가 처음 또는 마지막 k개 위치에서 서로 다를 경우 k + O(1) 상태를 사용하여 서로 구별할 수 있습니다.이것은 다항식적으로 작은 수의 쌍만이 초기 [1]O(log n) 위치에 차이가 없기 때문에 거의 모든 쌍이 로그 상태의 수로 서로 구별할 수 있다는 것을 의미합니다.
  • 만약 두 개의 이진어가 해밍 거리 d를 갖는다면, p = O(d log n)의 소수 p와 두 문자열이 다른 위치 i가 존재하며, i는 다른 어떤 차이의 위치와 모듈로 p와 같지 않다.i모듈로p에 합치하는 위치에서 입력 심볼의 패리티를 계산함으로써 O([1]d log n) 상태의 오토마톤을 이용해 단어를 구별할 수 있다.

레퍼런스

  1. ^ a b c d e f g Demaine, 에릭은 D;Eisenstat, 사라는;Shallit, 제프리, 윌슨, 데이비드 A.(2011년),"분리하는 것 말에 대하여", Descriptional 복잡함 공식적인 시스템의:13일 국제 워크숍 DCFS 2011년, Gießen/Limburg, 독일, 7월 25-272011집, 강의 노트 컴퓨터 과학으로, 6808, 하이델베르크:Springer-Verlag,를 대신하여 서명함. 147–157, vol.. ArXiv:1103.4513, doi:10.1007/978-3-642-22600-7_12, MR2910373, S2CID 6959459.
  2. ^ 를 클릭합니다Goralčík, P.; Koubek, V. (1986), "On discerning words by automata", Automata, Languages and Programming: 13th International Colloquium, Rennes, France, July 15–19, 1986, Proceedings, Lecture Notes in Computer Science, vol. 226, Berlin: Springer-Verlag, pp. 116–122, doi:10.1007/3-540-16761-7_61, MR 0864674.
  3. ^ 를 클릭합니다Robson, J. M. (1989), "Separating strings with small automata", Information Processing Letters, 30 (4): 209–214, doi:10.1016/0020-0190(89)90215-9, MR 0986823.
  4. ^ 를 클릭합니다Chase, Z. (2020), "A New Upper Bound for Separating Words", arXiv:2007.12097 [math.CO].
  5. ^ 를 클릭합니다Shallit, Jeffrey (2014), "Open Problems in Automata Theory: An Idiosyncratic View", British Colloquium for Theoretical Computer Science (BCTCS 2014), Loughborough University (PDF).