字母表 (计算机科学)
在计算机科学中，字母表是字符或数字的有限集合。最常见的字母表是二元字母表{0,1}。有限字符串是来自字母表的字符的有限序列；例如二元字符串是来自字母表{0,1}的字符构成的字符串。字符的无限序列也可以用来自一个字母表的元素来构造。 给定一个字母表\Sigma，我们写\Sigma^来指示在字母表\Sigma上的所有有限字符串的集合。这里的{}^指示Kleene星号算子。我们写\Sigma^\infty(偶尔\Sigma^\N或\Sigma…
标签：#词语组合
共 15 篇文章
形式语言
在数学、逻辑和计算机科学中，形式语言（）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面：语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。 语言的形式定义 字母表与字符串 语言定义在某一个特定的字母表上，字母表（经常记作 Σ ）可以为任意…
超排列
在组合数学中，n个符号的超排列（）是一个字符串，使得n个符号的所有排列均为它的子串。这些子串可以互相重叠。对于任意一个指定的n，超排列的长度存在一个最小值，最短的超排列称为最小超排列。 在1≤n≤5时，n个符号的最小超排列的长度是1!+2!+...+n!，分别是1、3、9、33和153，与之对应的字符串分别是1、121、123121321、123412314231243121342132413214321，以及： 12345123415…
達文波特-欣策爾序列
在组合数学中，達文波特–欣策爾序列是指对任意两个符号交替出现的次数作出限制的序列。達文波特–欣策爾序列其最大长度的界等于序列中不同符号的数目乘以一个渐近意义上很小但并非常数的因子，该因子取决于前述的交替次数上限。達文波特–欣策爾序列最早是由和于 1965 年为研究线性微分方程而定义的。该序列及其长度的渐近界继 一文之后成为了离散几何与几何算法分析领域的标准工具。 定义 有限序列 U = u1, u2, u3, ... 满足下列条件时被称…
贝亚蒂定理
在数论中，贝亚蒂定理（），又稱瑞利定理（）指：若 p,q \in \mathbb{R^+} ,p,q \not\in \mathbb{Q} 使得 \frac{1}{p} + \frac{1}{q} = 1，它們所生成的贝亚蒂數列（）P = \{\lfloor np \rfloor : n \in\mathbb Z^+ \}, Q=\{\lfloor nq \rfloor : n \in\mathbb Z^+\}，构成正整数集的一个劃分：…
字符串
字符串（），是由零个或多个字符组成的有限序列。一般记为s=a_1 a_2\dots a_n（0\leq n \lneq\infty）。它是编程语言中表示文本的資料型別;}-。 通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存…
HNN擴張
數學上，HNN擴張（）是組合群論中的一個基本構造法。HNN擴張是三名數學家Graham Higman、Bernhard Neumann、Hanna Neumann在1949年的論文Embedding Theorems for Groups提出。給定一個群中兩個同構子群及其間的群同構，這個構造法將這個群嵌入到另一個群中，令到所給定的群同構在新的群中成為共軛。 構造法 若G為群，有展示G = 〈S|R〉，又若 α : H → K是G的兩個子…
乒乓引理
群論中，乒乓引理（ping-pong lemma）給出了一個充分條件，保證一個群中數個子群所生成的群是這些子群的自由積。 歷史 使用乒乓引理的論證法可以追溯至19世紀後期，通常認為是菲利克斯·克萊因最先使用，他研究克萊因群的子群常常用到。雅克·蒂茨在他一篇1972年的文章中，證明著名的蒂茨兩擇性（Tits alternative）結果，一個主要工具就是乒乓引理。這結果指出任何有限生成的線性群，或是一個逼肖可解群（virtually so…
群的展示
在數學中，展示是定義群的一種方法。通過指定生成元的集合 S 使得這個群的所有元素都可以寫為某些這種生成元的乘積，和這些生成元之間的關係的集合 R。稱 G 有展示 :\langle S \mid R\rangle。 非正式的說，G 有上述展示如果它是 S 所生成的只服從關係 R 的“最自由的群”。正式的說，群 G 被稱為有上述展示如果它同構於 S 上的自由群模以關係 R 生成的正規子群的商群。 作為一個簡單的例子，n 階循環群有展示 :\…
自由么半群
在抽象代數裡，於一集合A上的自由幺半群是指一幺半群，其元素都是由A內零個或多個元素以串接之二元運算形成的有限序列(或字符串)。通常標記為A。其單位元為空字元串，標記為ε 或 λ。在A上的自由半群則指是A*內的子半群，其包含除了空字串外的所有元素。通常標記為A+。 更一般地，一抽象幺半群(半群)S被稱做是自由的，若其與某一集合上的自由幺半群(半群)同構。 如其名稱所述，自由幺半群(半群)為滿足定義了自由对象的泛性質的物件，在幺半群(半群)…
字度量
群論中，字度量是在群上的一種度量，就是一個方法去量度群中兩個元素之間的距離。給出群G的生成集S，每個元素都可以用S寫成很多個不同的字。例如設G是所有整數組成的群(\mathbb Z,+)，取S=\{\pm 1\}，3就可以寫成1+1+1，或者-1+1+1-1+1+1+1等字。每個字用了多少個S的元素，這就是字的長度，例如1+1+1的長度是3，-1+1+1-1+1+1+1的長度是7。可以用英文字來比喻：英文字的生成集是英文字母，字的長度就…
字 (群論)
在群論中，字是群的任何元素和它們的逆元寫成的乘積。例如，如果 x, y 和 z 是群 G 的元素，則 xy, z-1xzz 和 y-1zxx-1yz-1 都是集合 {x, y, z} 形成的字。字在自由群和展示理論中扮演重要角色，并是組合群論的中心研究對象。 定義 設 G 是群，并設 S 是 G 的子集。*S 形成的字*是如下形式的表達式 :s_1^{\epsilon_1} s_2^{\epsilon_2} \cdots s_n^{\e…
符号动力学
符号动力学是数学中研究符号动力系统的学科。在符号动力系统中，系统的状态可以表示成有限个抽象符号的无穷序列，由任一状态点的运动轨迹可以通过简单的移位规则来确定。 历史 关于符号动力学的起源可以追溯到雅克·阿达马在1898年的论文。 应用 延伸閱讀 Bruce Kitchens, Symbolic dynamics. One-sided, two-sided and countable state Markov shifts. Univer…
雙曲群
數學的幾何群論上，雙曲群是指一種帶有度量的群，符合雙曲幾何的某些性質。雙曲群是米哈伊爾·格羅莫夫於1980年代初所創的概念。 定義 群上的一個度量稱為左不變度量，如果群中任何兩個元素，被另外任一個元素左乘後，其間的距離仍保持不變。如果一個群有一個左不變度量，使得這個群按度量空間而言，是一個格羅莫夫雙曲空間，就稱之為雙曲群。 雙曲群中以字雙曲群最為常見。提到雙曲群時，通常就是指字雙曲群。一個有限生成群稱為字雙曲群（word hyperbo…
自由對象
在數學中，自由對象是抽象代數中的基本概念。就其通於各種代數結構（帶有限操作）而言，它也屬泛代數的一支，例子包括自由群、張量代數與自由格。在範疇論的框架下，可以將自由對象推廣為自由函子，這是遺忘函子的左伴隨函子。 自由函子 範疇論為自由對象提供了普遍框架。考慮一種代數結構（如群、模等等）的範疇\mathcal{C}。其上具有一個遺忘函子U: \mathcal{C} \to \mathbf{Set}，此函子將一個對象映至其下的集合；換言之，…