Free polynomial strong bimonoids
Manfred Droste and Zoltán Fülöp
最近,在加权自动机理论中,强双单体的重量结构引起了很大的兴趣;它们形成了半环的泛化,并与代数研究的近光相密切相关。 在这里,我们在一组不确定的 X 以及加法和乘法上定义多项式。 我们表明,通过这些操作,它们形成了一种右分配强双体,这种多项式强双体素在所有右分配强双硒素的类中是免费的,并且它既是左和右变。 我们通过纯粹的代数推理表明,两个任意术语是等价的,即权利分配强双单体的定律,只有当它们所代表的多项式与乘法的加法和同化性等同的法时,它们才具有等价性。 我们为构建表示多项式提供了有效的程序。 因此,我们了解到,任意术语mdulo法则的等价物可以在指数时间决定。 使用术语重写方法,我们表明每个术语可以简化为作为正常形式的唯一多项式。 我们还为 X 上的自由无效右分配多项式强双体类获得相应的结果。 我们构建了一个不称职的强双簧管,它在局部有限但不在局部有限,并在加权自动机理论中显示出它的应用。
Recently, in weighted automata theory the weight structure of strong bimonoids has found much interest; they form a generalization of semirings and are closely related to near-semirings studied in algebra. Here, we define polynomials over a set X of indeterminates as well as an addition and a multiplication. We show that with these operations, they form a right-distributive strong bimonoid, that this polynomial strong bimonoid is free over X in the class of all right-distributive strong bimonoid...
