ショートレックス注文

数学、特に形式言語理論において、ショートレックスとは、それ自体が完全に順序付け可能なオブジェクトの有限シーケンスの全順序付けである。ショートレックス順序付けでは、シーケンスは主に濃度（長さ）によってソートされ、最も短いシーケンスが最初になり、同じ長さのシーケンスは辞書式順序にソートされる。^{[1]ショートレックス順序付けは、}基数順序付け、長さ辞書式順序付け、軍事順序付け、系図順序付けとも呼ばれる。 ^[2]

完全に順序付けられたアルファベット上の文字列のコンテキストでは、 shortlex 順序は辞書式順序と同じですが、短い文字列が長い文字列の前に来る点が異なります。たとえば、英語のアルファベット上の文字列セットの shortlex 順序 (通常の順序) は [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa, aab, aac, ..., zzz, ... ] です。ここで、 ε は空の文字列を表します。

固定された有限アルファベット上のこの順序の文字列は、自然数と1対1の順序保存対応に配置することができ、数値を表すための全単射記数法を与えます。^{[3]ショートレックス順序は、}自動群の理論でも重要です。^[4]

参照

段階的辞書順

参考文献

^ シプサー、マイケル(2012)。計算理論入門(第3版)。ボストン、マサチューセッツ州: Cengage Learning。p. 14。ISBN 978-1133187790。
^ Bárány, Vince (2008)、「決定可能な MSO 理論を持つ自動 ω ワードの階層」、RAIRO 理論情報学および応用、42 (3): 417–450、doi :10.1051/ita:2008008、MR 2434027。
^ Smullyan, R. (1961)、「9. 辞書式順序; 整数の n 進表現」、形式システムの理論、数学研究年報、第 47 巻、プリンストン大学出版、pp. 34–36。
^ エプスタイン、デビッド BA ;キャノン、ジェームズ W. ; ホルト、デレク F. ; レヴィ、シルヴィオ VF ;パターソン、マイケル S. ;サーストン、ウィリアム P. (1992)、グループでのワード処理、ボストン、マサチューセッツ州: ジョーンズアンドバートレットパブリッシャー、p. 56、ISBN 0-86720-244-0、MR 1161694。

[1] シプサー、マイケル(2012)。計算理論入門(第3版)。ボストン、マサチューセッツ州: Cengage Learning。p. 14。ISBN 978-1133187790。

[2] Bárány, Vince (2008)、「決定可能な MSO 理論を持つ自動 ω ワードの階層」、RAIRO 理論情報学および応用、42 (3): 417–450、doi :10.1051/ita:2008008、MR 2434027。

[3] Smullyan, R. (1961)、「9. 辞書式順序; 整数の n 進表現」、形式システムの理論、数学研究年報、第 47 巻、プリンストン大学出版、pp. 34–36。

[4] エプスタイン、デビッド BA ;キャノン、ジェームズ W. ; ホルト、デレク F. ; レヴィ、シルヴィオ VF ;パターソン、マイケル S. ;サーストン、ウィリアム P. (1992)、グループでのワード処理、ボストン、マサチューセッツ州: ジョーンズアンドバートレットパブリッシャー、p. 56、ISBN 0-86720-244-0、MR 1161694。