쇼트렉스 순서

Shortlex order

수학에서, 그리고 특히 형식 언어 이론에서, 쇼트렉스는 그 자체가 완전히 순서가 될 수 있는 유한한 물체의 순서에 대한 총 순서다.숏플렉스 순서에서는 주로 가장 짧은 시퀀스를 가진 카디널리티(길이)에 따라 시퀀스를 정렬하고, 같은 길이의 시퀀스를 사전순으로 정렬한다.[1]숏렉스 순서는 라딕스, 길이 사전, 군사 또는 족보 순서라고도 한다.[2]

완전히 순서가 정해진 알파벳 문자열에 있는 문자열의 맥락에서, 짧은 문자열 순서는 긴 문자열보다 짧은 문자열이 앞선다는 점을 제외하면 사전 순서와 동일하다.예를 들어 영어 알파벳에 있는 문자열 집합의 쇼트렉스 순서(평소의 순서로)는 [ is, a, b, c, ..., z, ab, ac, ..., zz, aaa, aab, aac, ..., zz, ]이며 여기서 ε은 빈 문자열을 나타낸다.

고정된 유한 알파벳에 대한 이 순서의 문자열은 음이 아닌 정수와 일대일 순서가 유지되는 정수로 배치될 수 있으며, 숫자를 나타내기 위한 주관적 숫자 시스템을 제공한다.[3]숏렉스 순서는 자동군 이론에서도 중요하다.[4]

참조

  1. ^ Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: Cengage Learning. p. 14. ISBN 978-1133187790.
  2. ^ Bárány, Vince (2008), "A hierarchy of automatic ω-words having a decidable MSO theory", RAIRO Theoretical Informatics and Applications, 42 (3): 417–450, doi:10.1051/ita:2008008, MR 2434027.
  3. ^ Smullyan, R. (1961), "9. Lexicographical ordering; n-adic representation of integers", Theory of Formal Systems, Annals of Mathematics Studies, vol. 47, Princeton University Press, pp. 34–36.
  4. ^ Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word processing in groups, Boston, MA: Jones and Bartlett Publishers, p. 56, ISBN 0-86720-244-0, MR 1161694.


Stub icon

이 대수 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.