사전순서

수학에서 사전순서 또는 사전순서( 어휘순서 또는 사전순서라고도 함)는 사전의 알파벳순서를 순서의 기호순서에 따라 또는 보다 일반적으로 순서가 완전히 정해진 집합의 요소 순서에 따라 일반화한 것이다.

사전순서의 몇 가지 변형과 일반화가 있다.하나의 변형은 원소를 고려하기 전에 시퀀스의 길이를 비교함으로써 길이가 다른 시퀀스에 적용된다.

조합학에서 널리 사용되는 또 다른 변종은 유한 집합에 전체 순서를 할당하고 하위 집합을 증가 순서로 변환하여 주어진 유한 집합의 하위 집합을 명령하며, 여기에는 사전 순서가 적용된다.

일반화는 부분적으로 주문된 세트의 데카르트 제품에 대한 주문을 정의한다. 이 주문은 데카르트 제품의 모든 요소가 완전히 주문된 경우에만 총 주문이다.

동기부여와 정의

사전의 단어(일부 언어에서 사용되는 단어 집합)는 사전과 백과사전에서 사용되는 전통적인 순서를 가지고 있는데, 이 순서는 단어를 만드는 데 사용되는 기호의 알파벳의 기본 순서에 따라 달라진다.어휘순서는 기초 기호 순서에 따라 단어순서를 공식화하는 한 방법이다.

형식적인 개념은 알파벳이라 불리는 유한 집합 $A$ 로 시작되는데, 이것은 완전히 순서가 정해진다.즉, A에서 동일한 $기호$ 가 아닌 두 개의 기호 $a$ 와 $b$ 에 대해, $a$ < b> $또는$ b < $a$ .

$A$ 의 단어는 $A$ 의 유한한 기호 시퀀스로서, 하나의 기호를 포함하는 길이 1의 단어, 2개의 기호가 포함된 길이 2의 단어 등을 포함하며, 기호가 전혀 없는 $\varepsilon$ 빈 순서 $\varepsilon$ $\varepsilon$ 을 포함하기도 한다.이 모든 유한한 단어의 집합에 있는 사전 순서는 다음과 같이 단어의 순서를 정한다.

같은 길이의 두 개의 다른 단어인 $a$ = $aa 12 ... a$ 와_k b = $bb 12 ... b$ 를_k 볼 때, 두 단어의 순서는 첫 번째 단어 $i$ 에서 기호의 알파벳 순서에 따라 달라진다(단어의 시작부터 계산). a $i$ 는 알파벳 $A$ 의 기초 순서에 있는 < $b i$ >의_i 경우만 해당된다.
두 단어의 길이가 다를 경우, 일반적인 사전 순서는 단어의 길이가 같을 때까지 끝에 "빈칸"( $A$ 의 모든 요소보다 작은 것으로 취급되는 특수 기호)으로 짧은 단어에 패드를 씌운 다음, 앞의 경우와 비교한다.

그러나 조합학에서는 두 번째 경우에 다른 규칙이 자주 사용되는데, 여기서 짧은 순서는 항상 긴 순서보다 작다.사전 순서의 이러한 변형을 숏렉스 순서라고 부르기도 한다.

사전순으로 보면 다섯 번째 글자('a'와 'p'에서 먼저 다르기 때문에 '톰슨' 앞에 '토마스'라는 단어가 나타나며, 알파벳에서 'p'라는 글자 앞에 'a'가 나온다.첫 번째 차이이기 때문에 이 경우 다섯 번째 문자가 알파벳 순서에 대한 "가장 중요한 차이"가 된다.

사전순서의 중요한 특성은 각 $n$ 에 대해 길이 $n$ 의 단어 집합이 사전순서에 의해 잘 정렬되어 있다는 것이다. 즉, 길이 $n$ 의 모든 감소 순서는 유한하다(또는 동등하게, 모든 비어 있지 않은 부분집합은 최소 요소를 가진다.^[1]^[2]모든 유한한 단어들의 집합이 잘 정돈되어 있다는 것은 사실이 아니다. 예를 들어, 무한한 단어들의 집합은 {b, ab, aab, aab, aaab, ...}에는 사전 기록학적으로 가장 초기 요소가 없다.

숫자 시스템 및 날짜

사전 순서는 사전뿐만 아니라 숫자나 날짜에도 흔히 쓰인다.

로마 숫자 체계의 단점 중 하나는 두 숫자 중 어느 것이 더 작은지 항상 즉각적으로 명백하지 않다는 것이다.반면 힌두-아랍 수계의 위치 표기법으로 숫자를 비교하는 것은 음이 아닌 정수의 자연 순서는 어휘순서의 변형된 쇼트렉스(tortlex)와 같기 때문에 쉽기 때문이다.실제로 위치 표기법에서는 음이 아닌 정수를 숫자 자릿수의 순서로 나타내며, 숫자가 더 많거나(선행 0을 표시) 자릿수가 같거나 차이가 큰 첫 번째(가장 유의한) 자릿수가 같으면 정수가 다른 정수보다 크다.

십진법 표기법으로 표기된 실제 숫자의 경우, 십진법 왼쪽의 부분을 전과 같이 비교하고, 십진법 오른쪽의 부분을 십진법 순서와 비교하는 등 약간 다른 변형이 같을 경우 십진법 오른쪽의 부분을 십진법 순서와 비교한다.이 맥락에서 패딩 '공백'은 후행 "0" 자리수다.

음수까지 고려하면 음수 비교 순서를 거꾸로 해야 한다.이것은 보통 인간에게는 문제가 되지 않지만, 컴퓨터를 위한 것일 수도 있다(표지판을 테스트하는 데는 시간이 좀 걸린다).이것은 컴퓨터에서 서명된 정수를 나타내기 위해 두 개의 보완 표현을 채택하는 이유 중 하나이다.

사전 편찬 순서를 사용하지 않는 또 다른 예는 날짜에 대한 ISO 8601 표준에 나타나며, 이 표준은 날짜를 YYYY-MM-DD로 표현한다.이러한 형식 지정 방식은 날짜를 나타내는 문자 시퀀스의 사전 사전 순서가 연대순과 일치한다는 장점이 있다. 즉, 이전 CE 날짜는 9999년까지의 이후 날짜보다 사전순으로 작다.이 날짜 순서는 별도의 구분 알고리즘의 필요성을 없애서 날짜의 전산 정렬을 더 쉽게 한다.

단어의 모노이드

알파벳 $A$ 보다 단어의 모노이드는 A보다 $자유$ 로운 모노이드다.즉, 모노이드의 원소는 $A$ (빈 시퀀스, 길이 0의 원소 포함)의 유한 순서(단어)이며, 연산(복수)은 단어의 결합이다. $u$ 라는 단어는 $v$ = $uw$ 와 같은 $단어$ 가 있을 경우 다른 단어 $v$ 의 접두사(또는 'truncation')이다.이 정의에 따르면 빈 단어( $\varepsilon$ ${\displaystyle \varepsilon$ )는 모든 단어의 접두사이며, 모든 단어의 접두사( $w$ = $=\varepsilon$ ${\displaystyle =\varepsilon })$ 이며, $=\varepsilon$ 이러한 경우를 제외하려면 주의해야 한다.

이 용어를 사용하면 사전 순서에 대한 위의 정의가 보다 간결해진다. $부분적$ 으로 또는 완전히 주문된 집합 $A$ 와 $A$ 에 대한 $a$ 와 $b$ 의 두 단어가 비어 있지 않은 경우, 다음 조건 중 하나 이상이 충족되는 경우 사전순으로 " $b "$ 가 표시된다.

$a$ 는 $b$ 의 접두사다.
$u$ , $v$ , $w$ (아마도 비어 있을 것이다)라는 단어와 A의 $x$ 와 $y$ 라는 요소가 있다.

x < y

a = uxv

b = uyw

이 정의의 접두사 조건 때문에 $\varepsilon$ $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ < $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ b $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ , $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ {\ $displaystyle \var렙실론$ <b\,\,{\ $text$ ${모든$ $}$ $b\neq \$ $var렙실론$ $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ }}}이 $\varepsilon <b\,\,{\text{ for all }}b\neq \varepsilon ,$ (가 $)$ 빈 단어라는 $\varepsilon$ 점에 유의하십시오.

$\,<\,$ ${\$ 이 $\,<\,$ (가) A, ${\displaystyle$ $A$ $,}$ 에 대한 총 $A.$ 이라면 $A,$ A $.$ {\ $displaystyle$ A $}$ 의 단어에 대한 사전순서도 마찬가지지만 $A.$ , 일반적으로 $알파벳$ A{\ $displaystyty$ A}의 순서가 잘 정돈되어 있다고 $A$ 해도 이는 순서가 좋지 않다.예를 들어 $A =$ { $a,$ b $}$ 인 경우 { $ab n$ $n$ ≥ 0, $b$ > $}}$ 언어에는 사전 순서에서 최소 요소가 없다 $.$ $< aab < ab < b$ .

많은 어플리케이션들이 주문을 잘해야 하기 때문에 사전 주문의 변형이 자주 사용된다.숏렉스 또는 준사전적 순서라고도 하는 이 순서는 단어의 길이를 먼저 고려하는 데 있다( $길이(a) <길이(b),$ 그 $a<b$ 에 $a<b$ < $(b)>,$ 길이가 같으면 사전적 $순서$ 를 사용하는 데 있다. $A$ 의 주문이 잘 주문되어 있다면, 숏렉스 주문도 마찬가지다.^[2]^[3]

데카르트 제품

사전 순서는 주문된 세트의 카르테시안 제품에 대한 주문을 정의하는데, 이것은 이 모든 세트가 완전히 주문되었을 때의 총 주문이다.데카르트 제품 $E_{1}\times \cdots \times E_{n}$ $E_{1}\times \cdots \times E_{n}$ $E_{1}\times \cdots \times E_{n}$ $E_{1}\times \cdots \times E_{n}$ × $E_{1}\times \cdots \times E_{n}$ × $E_{1}\times \cdots \times E_{n}$ n ${\$ 의 요소는 모든 $i$ . ${\displaystyle E_$ ${n$ $}$ 에 $i.$ $E_{i}$ i ${\displaystystyle$ $E_{i}$ {i $}$ 에 $i$ ^th 속하는 시퀀스열이다 $E_{1}\times \cdots \times E_{n}$ .순서에서 같은 순위에, 사전 순서는 주문된 세트의 카르테시안 제품까지 확장된다.

특히 부분적으로 정렬된 두 개의 세트 $A$ $A$ 및 $A$ $B$ , $B$ 을 $B,$ (를) 지정하면 Cartesian 제품 $A\times B$ $A\times B$ $A\times B$ ${\displaystyle A\times$ B $}$ 의 사전 순서는 다음과 같이 정의된다 $A\times B$ .

(a,b)\leq \왼쪽(a^{\premy },b^{\premy }\premy }{\text{} 또는 }}\premy(a=a^{\premium }{\b\leq{}\premym }\right)},}}만 해당), {

그 결과는 부분 순서.A{A\displaystyle}과 B{B\displaystyle}각 완전히 명령을 받았다, 그때 그 결과는 전체 주문이기도 하다.그들의 제품 주문의 두가지가 전체적으로 주문한 세트의 사전 편집 순서는 따라서 일종의 선형 확장이다.

만약 그 가족은 비음의 정수에 의해, 또는 더 일반적으로 정돈된 집합에 색인되어 있는 사람은 주문한 세트의 무한한 가족의 데카르트 곱에, 마찬가지로 사전식 순서 규정할 수 있습니다.이것은 일반화된 불쌍한 사전 편찬자 주문은 총 경우 각 경제 요소 세트 완전히 명령을 받는다.

의 한정된 사건과 달리 well-orders의 무한 승적 것을 시사하는 사전 편집 명령에 의해 well-ordered지 않다.예를 들어, 셀 수 있게 무한한 이진 시퀀스(정의에 의해 함수의non-negative 정수에서{0,1}에,{){0,1\},\displaystyle}은 칸토어 공간{0,1}ω로{){0,1\}^{\omega}\displaystyle} 알려진)의 집합을 가지고 있는 시퀀스의 부분 집합이 정확하게 하나 1{\display 그 선두의 원을 갖지 않다.스타일 1}(그것은,{10만..., 010000..., 001000...}),{0< 1\displaystyle,}때문에 100000명 이상이 사전 편집 명령에 따라 적어도 요소 0개체에 의해 야기되는 1을 가지지 않는다...>010000...>001000...>은 무한한 남하 체인점이다.[1]마찬가지로 무한한 사전 편찬 상의 제품 때문에 011111Noetherian이 아니야...<>101111...<>110111...<>...무한 ascending 체인점이다.

순서가 잘 지정된 집합에 대한 기능

{Y\displaystyle}그들은 이에 따라 사전 편집 명령에 의해, 그리고 그런 두가지 기능을 위해{\displaystyle f}조의 주문할 수 있도록 잘 짜여진 집합 X{X\displaystyle}에서 완전히 명령 세트 Y{Y\displaystyle}에 기능은 시퀀스 Y의 요소들의 X{X\displaystyle}로 인덱싱 되. 확인될 수 있다.G, 그 불쌍한 사전 편찬자 위해 따라서 그들의 가치에 의해 가장 작은 경우 결정된다가 gf())≠()).{\displaystyle f())\neq g()){\displaystyle)}{\displaystyle g,}.}

$Y$ $Y$ 도 순서가 잘 되어 $Y$ $있고$ X{\ $displaystyle$ X $}$ 도 $X$ 유한하다면 결과 순서가 순서가 순서가 된다.위와 같이 $X$ $X$ 이 $X$ (가) 무한인 경우에는 그렇지 않다.

유한 부분 집합

빨간색 사각형 집합으로 표시된

\{1,\ldots ,6\},

\{1,\ldots ,6\},

{

\{1,\ldots ,6\},

\{1,\ldots ,6\},

\{1,\ldots,6\

의 3-제목 순서는 시퀀스(파란색)를 증가시키거나 표시기 함수로 10진수 표기법(회색)으로 변환한다.회색 번호는 또한 콜렉시컬 순서로

\{1,\ldots ,6\},

번호가

\{1,\ldots ,6\},

{1,

\{1,\ldots ,6\},

\{1,\ldots ,6\},

{\

displaystyle

\{

1,\ldots,6\},}

의 모든 하위 집합에서 하위 집합의 순위가 된다.사전(lex)과 콜렉티브(colex) 주문은 상단에, 해당 역순(rev)은 하단에 각각 있다.
주문에서 역순으로 넘어가거나, 아래가 아닌 아래를 읽거나, 빨간색과 흰색을 교환하는 방식으로 지나간다.

콤비네이터학에서는 흔히 열거해야 하므로 주어진 $집합$ S $.$ {\ $displaystyle$ S.}의 유한 부분 집합을 주문하기 위해 $S.$ $보통$ S $.$ {\ $displaystyle S.}$ 에서 주문을 선택한다 $S.$ . $그러면$ S {\\ $displaystyle$ S $}$ 의 부분 집합을 정렬하는 것은 그것을 증가하는 순서로 변환하는 것과 같다 $S$ .결과 순서에 대한 사전 순서는 따라서 하위 집합에 대한 순서를 유도하며, 이를 사전 순서라고도 한다.

이러한 맥락에서, 일반적으로 사람들은 숏렉스 순서와 같이 카디널리티에 따라 하위 집합을 먼저 정렬하는 것을 선호한다.따라서 다음에서는 고정 추기경의 하위 집합에 대한 명령만 고려할 것이다.

예를 들어 정수의 자연순서를 이용하여 $S=\{1,2,3,4,5,6\}$ = $S=\{1,2,3,4,5,6\}$ { $S=\{1,2,3,4,5,6\}$ , $S=\{1,2,3,4,5,6\}$ , $S=\{1,2,3,4,5,6\}$ , $S=\{1,2,3,4,5,6\}$ , 5, $S=\{1,2,3,4,5,6\}$ ${\displaystyle S=\{1,2,$ 3, $4,5,6\}$ 의 세 가지 요소의 하위 집합에 대한 사전순서는 다음과 같다 $S=\{1,2,3,4,5,6\}$ .

123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <

234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456

.

자연수의 주어진 카디널리티의 유한 부분 집합을 주문하는 경우, 모든 초기 세그먼트가 유한하기 때문에 콜렉시컬 순서(아래 참조)가 종종 더 $n$ 하다 $.$ 따라서 콜렉시컬 순서에서는 $자연수$ 와 n $n$ {\ $displaystyn$ n $}$ 자연수 집합 사이의 순서 이형성을 정의하기 때문이다.사전 순서는 그렇지 않은데, 예를 들어 사전 순서와 함께 매 $n>2.$ > 2. ${\displaystyle n>2$ 에 대해 $12n<134$ $12n<134$ < $>[\displaystyle 12n<134}$ 이 $($ 가) 있다 $n>2.$ $}$

$\mathbb {Z} ^{n}$ $\mathbb {Z} ^{n}$ ${\$ 의 그룹 주문

$Z$ $\mathbb {Z} ^{n}$ ${\$ 은 $\mathbb{Z } ^{n}$ $n,$ (는) n $,$ ${\displaystyle$ n $,$ 이 요소의 순서는 n $n$ 이고 $n$ , 연산은 덧셈이다. $\mathbb {Z} ^{n}$ $\mathbb {Z} ^{n}$ ${\$ ^{ $n}}$ 의 그룹 주문은 총 주문으로, 추가와 호환되는 총 주문이다 $\mathbb {Z} ^{n}$ .

{\\display a<b\property {\text{만약에 그리고 만약 }\properties a+c[b+c]인 경우에만 표시.}

사전순서는 $\mathbb {Z} ^{n}.$ $\mathbb {Z} ^{n}.$ . $\mathb {Z} ^{n$ 의 그룹순서다. $}$

사전 순서는 $\mathbb {Z} ^{n}.$ $\mathbb {Z} ^{n}.$ n . $\mathbb {Z} ^{n}.$ {\ $displaystyle \mathb {Z}$ ^{ $n}$ 의 모든 그룹 주문의 특성을 나타내는 데 사용될 수 있다. $}}$ 실제로 $\mathbb {Z} ^{n}.$ ^[4]^[5] 실제 계수를 $가진$ n {\ $displaystyle$ n $}$ 선형 $n$ 형태는 $\mathbb {Z} ^{n}$ ${\$ ^{ $n}}$ 에서 $\mathbb{Z } ^{n}$ $\mathbb {R} ^{n},$ $\mathbb {R} ^{n},$ {\ $displaystyle \mathb {R} ^{n}}$ 까지 지도를 정의하십시오 $\mathbb {R} ^{n},$ (형식이 선형적으로 독립되어 있는 경우에도 아래를 참조).이 지도 영상의 사전 순서는 $\mathbb {Z} ^{n}.$ n . ${\displaystyle \mathb$ { $Z} ^{n}}}$ 로비아노의 정리로는 $\mathbb {Z} ^{n}.$ 모든 그룹 순서가 이런 식으로 얻어질 수 있다는 것이다.

더 정확히 $\mathbb {Z} ^{n},$ , Z $\mathbb {Z} ^{n},$ , ${\displaystyle$ $s\leq n$ \ $mathb {Z} ^{n}}$ 에 그룹 순서가 주어지면 Z $s\leq n$ ${\$ $displaystyle s\leq$ n $}$ 및 s $s\leq n$ ${\$ $displaystyle$ $s}$ 선형 $\varphi$ 가 $s$ 존재하는데 $\mathbb {Z} ^{n},$ , $\mathbb {Z} ^{n}$ 는 Z $\mathbb {Z} ^{n}$ ${\$ ^{n $}}}{n$ }}}}}}}}에서 유도된 $\varphi$ 실제 계수가 된다. $\mathbb {R} ^{s}$ $\mathbb {R} ^{s}$ ${\$ 에는 다음과 같은 속성이 있다 $\mathbb {R} ^{s}$ .

$\varphi$ $\varphi$ 이(가) 주입식임 $\varphi$ ;
$\mathbb {Z} ^{n}$ ${\$ $displaystyle \mathb {Z} ^{n}}$ 에서 $\varphi$ ${\displaystyle$ $\$ $varphi }$ 의 영상에 이르는 $\mathbb {Z} ^{n}$ 결과 이형성(isomorphism)은 $\varphi$ 영상에 $\mathbb {R} ^{s}.$ . {\ $displaysty \$ mathb {R} $^{s}$ 의 사전적 순서가 장착된 경우의 순서 이형성이다. $}$

콜렉시그래픽 순서

{1,...,5}의 24개 순열 순서(파란색).공lex 순서에 따른 순열의 반전 벡터(빨간색)는 revcolex 순서에 있으며, 그 반대의 경우도 revcolex 순서에 있다.

콜렉시그래픽(collicographic) 또는 코렉스(colex) 순서는 왼쪽에서 오른쪽으로 읽는 대신 오른쪽에서 왼쪽으로 유한한 시퀀스를 읽음으로써 얻어지는 사전 순서의 변형이다.보다 정확하게, 두 시퀀스 사이의 사전 순서는 다음에 의해 정의된다.

aa 12 ... a k lex

<

bb 12 ...

b k

만약

a

와_i_i

b

가_i 다른 첫

번째

i에 대해 <

b

를_i 말한다면,

편찬 순서는 에 의해 정의된다.

aa 12 ... a k colex

<

bb 12 ... b k

만약

a

가_i_i

a

와_i b가 다른 마지막

i

의

경우 i .

일반적으로 콜렉티브 순서(collicographic order)와 사전 순서(rexicographic order)의 차이는 그리 크지 않다.그러나 일반적으로 부분 집합 코딩에 대해 시퀀스 증가를 고려할 때 두 순서는 유의하게 다르다.

예를 들어, 두 개의 자연 정수의 증가하는 시퀀스(또는 세트)를 정렬하기 위해 사전 순서는 다음과 같이 시작한다.

12 < 13 < 14 < 15 < ...

< 23 < 24 < 25 < ...

< 34 < 35 < ... < 45 < ...

,

그리고 콜렉시그래픽 순서는

12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...

.

주어진 길이의 시퀀스를 증가시키기 위한 균사체 순서의 주요 특성은 모든 초기 세그먼트가 유한하다는 것이다.즉, 주어진 길이의 시퀀스를 증가시키기 위한 콜록시적 순서는 자연수와의 순서 이형성을 유도하고, 이러한 시퀀스를 열거할 수 있게 한다.이것은 콤비네이터학에서 자주 사용되는데, 예를 들어 크러스칼-카토나 정리증명에 사용된다.

모노미알스

다항식들을 고려할 때, 일반적으로 용어의 순서는 중요하지 않다. 그 추가는 상응하기 때문이다.그러나 다항식 긴 분할과 같은 일부 알고리즘은 용어 순서를 특정해야 한다.다변량 다항식 알고리즘의 대부분은 단항식 순서를 선택해야 하는 개념인 그뢰브너 베이스(Gröbner base), 즉 단항식 구조와 호환되는 전체 순서(total order)와 관련이 있다.여기서 "호환성"은 모노이드 연산이 승수적으로 표시된 $a<b{\text{ implies }}ac<bc,$ 경우 < $a<b{\text{ implies }}ac<bc,$ >가 $a<b{\text{ implies }}ac<bc,$ c < $a<b{\text{ implies }}ac<bc,$ c $a<b{\text{ implies }}ac<bc,$ , ${\displaystyle$ a $<b{\text{}$ 를 의미함을 의미한다.이러한 양립성은 단일어에 의한 다항식의 곱이 용어의 순서를 바꾸지 않는다는 것을 의미한다.그뢰브너 기지의 경우, 추가 조건이 충족되어야 하는데, 즉 모든 비 상수 단수체가 단수 $1$ 보다 크다는 것이다.그러나 접선 원뿔 계산을 위한 알고리즘과 같은 다른 관련 알고리즘에는 이 조건이 필요하지 않다.

그뢰브너 베이스는 일정한 수의 변수의 다항식에 대해 정의되기 때문에, 단항(예: $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ x $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ 4 x $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ {\ $displaystyle x_{$ 1} $x_{2}^{3}x_{4}x_{5}^{$ $5}^{2$ $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ 을 지수 벡터로 식별하는 것이 일반적이다 $.$ $n$ 이 변수의 수인 경우, 모든 단수 순서는 $\mathbb {Z} ^{n}$ Z $\mathbb {Z} ^{n}$ ${\$ \ $mathb$ ${N}$ ^{ $n$ $}$ 의 단수 순서에 대한 $\mathbb {N} ^{n}$ $\mathbb {N} ^{n}$ n {\ $displaystyle \mathb$ {Z $}{n}}$ ^{n $}}$ 의 제한이다( $\mathbb {Z} ^{n}$ 분류는 위의 $\mathbb {Z} ^{n},$ $\mathbb {Z} ^{n},$ § $\mathbb {Z} ^{n},$ 순서 $\mathbb {Z} ^{n},$

이러한 인정된 명령 중 하나는 사전적 명령이다.역사적으로 그뢰브너 기지를 규정하는 데 가장 먼저 사용되었으며, 사전적 질서와도 관련이 있는 다른 질서와 구별하기 위해 순수 사전적 질서로 불리기도 한다.

또 다른 것은 먼저 총도를 비교한 다음 사전순으로 갈등을 해결하는 것이다.이 순서는 일반적으로 어휘 순서 또는 역 사전 순서 중 하나가 더 나은 특성을 가지기 때문에 널리 사용되지 않는다.

학위 역 사전 순서는 총 학위를 먼저 비교하고, 총 학위가 동일할 경우 콜렉티브 순서 역순을 사용하는 데도 구성된다.즉, 두 개의 지수 벡터가 주어진 경우, 하나는

[a_{1},\ldots ,a_{n}]<[b_{1},\ldots ,b_{n}]

어느 것이든

a_{1}+\cdots +a_{n}<b_{1}+\cdots +b_{n}

또는

a_{1}+\cdots +a_{n}=b_{1}+\cdots +b_{n}\cdots {\data.{n}\cdots {\cdomes a_{i}}}{i}}}{}\text{}}{}}}}}}{}}}}}{{{{{}}}}}}}}}}}}}}}}}}}}}}}}\text}}}}}}}}}}}}}}}}}

이 주문의 경우, 도 1의 단수 순서는 해당 인디테마네이트와 동일하다(역 사전 순서를 사용하는 경우에는 그렇지 않다).총도가 같은 두 변수에서 단수들을 비교하는 경우, 이 순서는 사전 순서와 동일하다.변수가 더 많은 경우는 그렇지 않다.예를 들어, 3개 변수 중 2도 단수 벡터의 경우, 1은 역독성 순서에 대해 다음과 같이 한다.

[0,0,2]<[1,1]<[1,0,1]<[1,0]<[1,0,0]

사전 순서의 경우, 동일한 지수 벡터가 다음과 같이 정렬된다.

[0,0,2]<[0,1,1]<[1,0,1]<[1,1,0]<[2,0,0].

역사전 사전 순서의 유용한 특성은 동종 다항식이 선행 단항(더 큰 단항)이 이 최소 불규칙의 배수인 경우에만 최소 불규칙의 배수라는 것이다.

참고 항목

참조

^ ^a ^b Egbert Harzheim (2006). Ordered Sets. Springer. pp. 88–89. ISBN 978-0-387-24222-4.
^ ^a ^b Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.
^ Calude, Cristian (1994). Information and randomness. An algorithmic perspective. EATCS Monographs on Theoretical Computer Science. Springer-Verlag. p. 1. ISBN 3-540-57456-5. Zbl 0922.68073.
^ 로비아노, L. (1985)다항식 링의 용어 순서.유럽 컴퓨터 대수학 총회 (pp. 513-517)에서.스프링거 베를린 하이델베르크.
^ Weispfenning, Volker (May 1987), "Admissible Orders and Linear Forms", SIGSAM Bulletin, New York, NY, USA: ACM, 21 (2): 16–18, doi:10.1145/24554.24557, S2CID 10226875.

외부 링크

위키다양성에서의 어휘 및 어휘순서와 관련된 학습 자료

[Harzheim-1] Egbert Harzheim (2006). Ordered Sets. Springer. pp. 88–89. ISBN 978-0-387-24222-4.

[BaaderNipkow1999-2] Franz Baader; Tobias Nipkow (1999). Term Rewriting and All That. Cambridge University Press. pp. 18–19. ISBN 978-0-521-77920-3.

[3] Calude, Cristian (1994). Information and randomness. An algorithmic perspective. EATCS Monographs on Theoretical Computer Science. Springer-Verlag. p. 1. ISBN 3-540-57456-5. Zbl 0922.68073.

[4] 로비아노, L. (1985)다항식 링의 용어 순서.유럽 컴퓨터 대수학 총회 (pp. 513-517)에서.스프링거 베를린 하이델베르크.

[5] Weispfenning, Volker (May 1987), "Admissible Orders and Linear Forms", SIGSAM Bulletin, New York, NY, USA: ACM, 21 (2): 16–18, doi:10.1145/24554.24557, S2CID 10226875.

[1]

[2]

[3]

[4]

[5]

Search

사전순서

네임스페이스

더

목차

동기부여와 정의

숫자 시스템 및 날짜

단어의 모노이드

데카르트 제품

순서가 잘 지정된 집합에 대한 기능

유한 부분 집합

$\mathbb {Z} ^{n}$ $\mathbb {Z} ^{n}$ ${\$ 의 그룹 주문

콜렉시그래픽 순서

모노미알스

참고 항목

참조

외부 링크

Search

사전순서

동기부여와 정의

숫자 시스템 및 날짜

단어의 모노이드

데카르트 제품

순서가 잘 지정된 집합에 대한 기능

유한 부분 집합

Z n {\displaystyle \mathb {Z} ^{n}}의 그룹 주문

콜렉시그래픽 순서

모노미알스

참고 항목

참조

외부 링크

$\mathbb {Z} ^{n}$ $\mathbb {Z} ^{n}$ ${\$ 의 그룹 주문