论文标题
布尔行动之星的状态复杂性
State complexity of the star of a Boolean operation
论文作者
论文摘要
怪物和修饰符是国家复杂性理论最近开发的两个概念。 怪物是一个自动机，其中从状态到状态的每个功能都由至少一个字母表示。修饰符是一组函数，允许人们将一组自动机转换为一个自动机。本文描述了一种一般策略，可用于计算许多操作的状态复杂性。我们在布尔操作的明星问题上说明了这一点。在怪物上应用修饰符后，将所得的自动机的状态吸收到组合对象：tableaux。我们研究了这些图表的组合，以推断状态的复杂性。具体而言，我们恢复了相交之星和联合之星的状态复杂性，并且还给出了对称差异之星的确切状态复杂性。 因此，我们协调搜索策略，以实现任何布尔操作的星星的状态复杂性。
Monsters and modifiers are two concepts recently developed in the state complexity theory. A monster is an automaton in which every function from states to states is represented by at least one letter. A modifier is a set of functions allowing one to transform a set of automata into one automaton. The paper describes a general strategy that can be used to compute the state complexity of many operations. We illustrate it on the problem of the star of a Boolean operation. After applying modifiers on monsters, the states of the resulting automata are assimilated to combinatorial objects: the tableaux. We investigate the combinatorics of these tableaux in order to deduce the state complexity. Specifically, we recover the state complexity of star of intersection and star of union, and we also give the exact state complexity of star of symmetrical difference. We thus harmonize the search strategy for the state complexity of star of any Boolean operations.
