The monoid of queue actions
The monoid of queue actions
复制标题
队列动作的幺半群
作者：
Martin Huschenbett;D. Kuske;Georg Zetzsche
我们将 fifo 队列的行为建模为由写入和读取序列引起的变换的幺半群。我们通过汇合和终止半图系统来描述这个幺半群，并研究它的一些基本代数性质，例如共轭。此外，我们表明，虽然有关其有理子集的几个属性是不可判定的，但它们的统一成员资格问题是 NLdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{文档}$${{mathsf {N}}}{{mathsf {L}}}$$end{文档}-完成。此外，我们提出了这个幺半群可识别子集的代数表征。最后，我们证明它不是瑟斯顿自动的。
We model the behavior of a fifo-queue as a monoid of transformations that are induced by sequences of writing and reading. We describe this monoid by means of a confluent and terminating semi-Thue system and study some of its basic algebraic properties such as conjugacy. Moreover, we show that while several properties concerning its rational subsets are undecidable, their uniform membership problem is NLdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${{mathsf {N}}}{{mathsf {L}}}$$end{document}-complete. Furthermore, we present an algebraic characterization of this monoid’s recognizable subsets. Finally, we prove that it is not Thurston-automatic.