有限幺半群计算与一致的广义星高度界
Finite Monoid Computations and a Uniform Generalized Star-Height Bound
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究正则语言的广义正则表达式星高度。作者声称：有限字母表上的每个正则语言，在同一字母表上都存在星高度至多十三的广义正则表达式。证明思路是把有限幺半群计算表示为仿射更新，并通过十二次连续分裂构造将其恢复。该结果给出一个统一常数界，属于形式语言与自动机理论中描述复杂度的研究。
- 作者声称每个正则语言在同一字母表上有星高度≤13的广义正则表达式
- 证明将有限幺半群计算表示为仿射更新并经十二次分裂构造恢复
- 给出正则语言广义星高度的统一常数上界
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
Every regular language over a finite alphabet has a generalized regular expression of star height at most thirteen over that same alphabet. We prove this uniform bound by representing finite monoid computations as affine updates and recovering them through twelve successive split constructions.
用户标记：未标记
固定编号：006bf18286ec975a
原文来源