LLLLLLL可在www.sciencedirect.com在线获取理论计算机科学电子笔记348（2020）23-41www.elsevier.com/locate/entcs有限代数结构米格尔·坎佩尔乔利1 巴勃罗·文图拉3FaMAF科尔多瓦国立大学阿根廷摘要这项工作处理的可定义性问题的quantier-free一阶公式在有限代数结构。我们的问题是CONP-完全的，并提出了一个决策算法的基础上的语义特征的可定义的关系作为那些保持同构的子结构。我们的方法还包括一个算法的设计，计算同构类型的元组在一个有限的代数结构。的算法的合理性和完整性的证明，以及评估其性能的实证测试。保留字：可定义性，逻辑，决策算法，复杂性1介绍给定一个逻辑，的模型论语义是一个函数，该函数为并且每个结构A 一组来自A的域的元组。这组元组被称为A中A的扩展，我们通常认为这些元组是使A中的A为真的解释，尽管这也是有意义的把它们看作是那些被挑选出来的，或者被命名的，由以π表示的属性。各种基本的计算问题从这个设置中产生，其中最突出的肯定是满足性问题，即对于给定的公式，是否存在模型A，使得A中的扩张非空。 模型检验问题，它包括计算，给定一个模型A和一个公式A，A中的公式A的扩展，也在计算逻辑中发挥了重要作用。第三个基本问题，也是我们在本文中关注的问题，是L的可定义性问题，它给出了一个有限模型A和一个1电子邮件地址：camper@famaf.unc.edu.ar2电子邮件：mauriciotellechea@gmail.com3电子邮件：pablogventura@gmail.comhttps://doi.org/10.1016/j.entcs.2020.02.0031571-0661/© 2020由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。24M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）23不⊆T∈T∈A的元组的集合R询问是否存在公式R，使得A中的R的扩张与R一致。由于这个问题的基本性质和它的应用，例如数据库理论，这个问题已经被研究了几个[11]和引用表达式的生成[10，4，3]。可定义性问题的计算复杂性也被研究了各种逻辑。文章[9]研究了经典命题逻辑的可定义性问题，在逆可满足性的名义下，证明了它在一般情况下对coNP是完全的他们还描述了问题所在的特殊句法情况P.在[5]中证明了对于一阶逻辑，可定义性问题是GI-完全的（在图灵约化下）。对于一阶逻辑的原始正片段，可定义性问题是上EXPTIME-完全的[12]，而对于基本模态逻辑[4]及其某些片段[3]，它是在P中。在文章[1]中，证明了对于具有纯关系词汇的一阶逻辑的无量化器片段，可定义性问题是coNP完全的，并且在同一篇文章中，证明了该问题的参数化版本对于复杂性类W是完全为了说明可定义性的概念，让我们看一个例子。设D=其中，n {t，T，u，uJ}，n，u j是下面描述的格，并且令R={（a，b）∈D2：a≤b}。uu′⊥图1. 点阵D我们想知道R在D中是否是无量化的。也就是说，如果在D的词汇表中存在一个无数量因子的公式<$（x，y），使得R={（a，b）∈D2：D<$<$（a，b）}。很容易看出公式<$（x，y）：=（x<$y）=y是有效的。接下来，考虑关系RJ={（n，u），（n，uJ），（n，T）};它在D中是无量化器可定义的吗？答案是否定的，原因如下注意，映射γ：{λ，T}→{u，T}是D的子格之间的同构，并且无量化器公式是保存在这样的地 图上。也就是说 ，如果（ x，y ）是quantier free 的， D 是quantier free的，则D是quantier free的，D是quantier free的。因此，对于任何结构，每一个可由无量化器公式定义的关系都由子结构之间的同构（我们称这些映射为次同构）来保持。 回到我们的例子，我们可以看到，（，）RJ但是（γ，γ）/RJ，所以RJ不被γ所表示，因此它在D中不是无量化的。有趣的是，这一标准的逆命题也适用于有限结构;即，如果A是有限结构，则关系R Ak在A中是无量化器可定义的当且仅当R被A的所有子同构保持（见下面的定理2.1在[2]中应用了无量化器可定义关系的这种特征，以获得一种算法，该算法决定了一阶逻辑的无量化器片段的可定义性问题，该片段具有纯粹的关系词汇（称为开放式M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2325变量{}。 我们写T∈ T为集合⊆--∈|的定义问题[2]）。在当前的说明中，它继续并补充了[2]中的工作，我们开发了一个基于相同语义特征化的算法，但用于代数词汇表（即，没有关系符号）。值得注意的是，在允许量化的一阶逻辑片段中，关系和代数可定义性问题崩溃了，因为以引入量化器为代价，每个公式都可以有效地转换为一个等价的非嵌套公式。然而，在无量化器的情况下，问题是不一样的，需要不同的算法策略。主要的区别在于，在代数情况下计算结构的子结构之间的同构，需要计算结构的子宇宙。在本文中，我们的算法决定可定义性的方法是基于这样的观察：计算由结构A中的元组a <$y（f的元素）生成的子单元与计算A中a <$的同构type并不遥远（见第4节）。除了提出上述算法，我们证明了代数词汇的量化自由定义问题的计算复杂性对于coNP是完全的。本文的结构如下。在下一节中，我们将固定符号并提供基本定义。第三节是对我们的复杂性结果的阐述。 在第4节中，我们介绍了计算代数中第5节给出了判定代数结构的无量化因子可定义性的算法。 在第6节中进行了一些实证测试，表明我们的算法在具有大量对称性的模型上表现得更好。最后，第7节提供了一个总结所获得的结果，以及进一步的研究方向所产生的发展，我们在这里。2预赛在本节中，我们提供一些基本的定义和fix符号。我们假设一阶逻辑的基本知识。有关详细说明，请参阅，例如，[7]的文件。给定一个一阶词汇表τ和k∈ω，设Tk表示深度为k的τ-项的集合，：=x1，x2，.，xn，.. .：=k ω k所有的τ项都是VAR。对于函数或关系符号s，我们写ar（s）表示s的arity。在本注记中，我们所关心的是代数词汇，也就是说，没有关系符号。在这种情况下，原子公式的形式为t=tJ，其中t和tJ是项。无量化器公式是原子公式的布尔组合。我们写（v1，...，vk）对于变量都包含在v1，.中的公式vk. 代数是代数词汇表的结构;代数由黑体字母表示（例如，A、B、C、.）和他们的宇宙对应的非粗体字母。给定一个代数A，一个公式n（v1，...，vk），以及元素n tsa<$=（a1， . 、a、k）Ak可以写为A=（a <$），如果在一个将vi映射到ai的赋值下，在A中为真。我们说一个子集R Ak在A中是无量化定义的（简称qf-可定义的），前提是存在无量化定义的一阶公式<$（x1，.， xk）在A的词汇表中，使得R={a<$∈Ak：A|=（a<$）}。26M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）23∈⊆∈ ∩∈⊆ →⊆--∈联系我们.在这篇文章中，我们研究了以下计算决策问题：QfDefAlg输入：一个有限代数A和一个目标关系R<$Ak。问题：R在A中是qf可定义的吗？设A是一个代数。一个子集S ∈ A是A的一个子论域，如果S是非空的，并且它在A的基本运算下是闭的。 F或元组a<$=（a1， . ，ak）Ak记为Sg（a<$）表示由y生成的A的子单位a1， . ，k. 设γ：dom γAA是一个函数。 我们说γ保持RAk，如果对于所有的（a1，...， ak）R（domγ）k我们 有（γa1，.，γak）R.函数γ是A的次同构，条件是γ是内射的，dom γ是A的子论域，并且γ对每个fτ保持f A的图。(Note A的一个子同构恰好是A的两个子结构之间的同构。）下面用子同构刻画qf-可定义性的结果在本文中起着中心作用。定理2.1[6，定理3.1]设A是任意一阶签名的有限模型，RAk。以下是等价的：• R在A中可由一个无量化器的一阶公式定义。• R被A的k-生成子结构之间的所有同构保持。3QfDefAlg是coNP完全的图是语言的一个模型G，它有一个二元关系E，使得EG是对称的和不对称的。文[1]证明了下述问题对于coNP是完全的。QfDef[图形]输入：一个有限图G和一个目标关系RGk。问题：R在G中是qf可定义的吗？图G=（G，E）的一个次同构是一个内射函数γ：domγ∈G→G使得（a，b）∈E当且仅当（γa，γb）∈E.定理3.1 QfDefAlg是coNP完全的.设G=（G，E）是有限图G的一个有限图，设G =（G，E）中的第一个不属于图G的两个顶点为0和1，则G =（G，E）中的顶点为0. 我们定义代数G∈：=（G其中f是二进制运算f（a，b）= <$1如果（a，b）∈E或a=b∈{<$0，<$1}000 元，否则可以直接检查：M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2327⊆|⟨⟩T ∈ T(i) 若γ是G的一个次同构，则γgiven的扩张γ（γ0）=γ0γ<$（<$1）=<$1是G <$1的一个次同构.(ii) 若δ是G的一个次同构，则δ[G]<$G且δ|G是的一个次同构G接下来我们证明了，G，R<$<$− →G，R是从QfDef[Graphs]到QfDefAlg的多项式时间（Karp）约简。显然，G可以在多项式时间内从G计算出来，所以仍然需要证明R在G中是qf可定义的，当且仅当R在G中是qf可定义的。固定一个有限图G和RGk。设R在G中不可qf-定义。然后，根据定理2.1，存在γ，G的一个次同构，它不保持R。现在(1)说γ是G的一个次同构，由于它不保持R，因此R在G中是不可qf-定义的。对于其余方向，假设R在G中不可qf定义。定理2.1又产生了G的一个不保持R的次同构δ。 由（2）可以得出，δG是G的一个不保持R的次同构;因此R在G中不是qf-可定义的。证明QfDefAlg在coNP中是定理的直接应用2.1. 事实上，每一个负面的例子 A、RQfDefAlg的双射证明了 满足条件的A的子集之间的γ在多时间w.r.t.中容易检查。的大小，R。Q从定理3.1的证明可以得出，QfDefAlg对具有单个二元交换运算的结构的限制对于coNP已经是完全的。4计算元组的同构类型在这一节中，我们给出了一个计算有限代数结构A中元组a ′的同构类型的算法，并证明它是正确的。我们从一些必要的定义和初步结果开始设A是有限代数，对每一个k∈ω，我们定义等价关系上Anbya<$k<$b当且仅当对所有项t，s∈Tk（x0， . ，xn−1）我们知道，tA（a<$）=sA（a<$）tA（<$b）=sA（<$b）.定义等价关系Anbya<$b当且仅当a<$k<$b对所有k∈ω。Fora<$∈AnletKa<$：=min{k∈ω：对所有的t∈Tk（x<$），有t<$ ∈Tk−1（x<$）suc h使得tA（a<$）=t<$A（a <$）}。注意，由于A是有限的，这个最小值总是存在的。引理4.1LetAbea有限代数a和a<$，<$b∈An。(i) 如果a<$Ka<$b，则对于任何项t（x<$），re是项t（x<$）l，其中l0并且假设t=f（t1，...， tr），其中eachti∈TK+j−1。 根据归纳性论点，有术语t_1，...，tr∈Tu其中u→<$b的次同构。4.1健全性和完整性对于X，变量名为{V，V，J，P，H，N}并且k∈{0， . ，K}，let• Xa<$，k是在算法1的运行中变量X的值，在k之后输入A，a<$while循环的执行。此外，给定A的函数符号的arityr，令ra'，k b是在具有输入A，a′的算法m1的运行中分配给变量T的值，一旦在for循环中固定了一个arityr（第10行），在第k次执行期间，while循环• 不30M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）23我们写Xa<$forXa<$，Ka<$，对于k>Ka<$we定义Xa<$，kto beXa<$. 在不引起混淆的情况下，省略子索引a ′。M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2331T算法1元组同构类型1个功能同种型（A，a′）2V=[a0， . . . ，an−1]dA是一个代数，a<$是来自A的元组3V′=[“x 0“，. ，4P=[B1， . ，Bk]的分区{0， . ， n−1}其中i，j在相同的块中，ocki=aj5H=sorted（[min（Bj）：Bj∈P]）d递增排序6N= H7arities =[r1，.，其中r1<. min（Ka<$，K<$b）保持s。(iv) Ta ket=f（t0， . ，tr−1）∈Tk+1且满足k+1≤Ka<$. 对于k=0，定义F0（xj）= j。 如果k ≥ 1，通过归纳假设我们有函数Fk，因此我们可以得到指数i0：=Fk（t0，ρk−1），.，ir−1：= Fk（tr−1，ρk−1）从t泛函和ρk（显然t0，.，tr−1可以作为t的函数得到，且ρk−1= ρk <$T 2）。如果k=0，取i0：=F0（t0），.，ir−1：=F0（tr−1）. 接下来，定义k−1t0：=VJk[i0].tr−1：=VJk[ir−1]，再一次注意，这些t可以通过函数得到，因为VJk可以通过函数从ρk得到。 此外，通过归纳，我们得到A（a′）=f（t≠0， . ） ，tr−1）A（a <$）.假设首先存在l∈{0， . r−1}su c h使得il∈Hk\Hk−1. 则il∈Nk，所以我是0， . ，ir−1 <$∈Tr，并且我们知道f（t<$0， . ，tr-1）isappdtoVJ，比如在while循环的第（k+1）遍期间具有索引j。 注意，只有j取决于A的签名和数字Tu。对于u，一个小于或等于坦河但是Tu只取决于Hk和Nk，而Hk和Nk又由ρk决定。因此，j可以作为t和ρk的函数获得，并且我们可以定义Fk+1（t，ρk）：在存在l∈{0， . . . ， r−1}su c h使得il∈Hk\Hk−1. 另一方面，我认为.. . ，ir−1∈Hk−1.然后，通过（i），我们已经知道，t=0， . ，t<$r−1∈Tk−1，且t husf（t<$0， . ，t<$r−1）∈Tk.因此，在这种情况下，我们可以定义Fk+1（t，ρk）：=Fk（f（t≠0， . ，tr−1），ρk−1）.(v) 首先注意，对于j≤k，我们有Pj是Pk对集合的限制=T<$M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2333∈∈B到。||||联系我们{0，.， |VJ|−1}。此外，Hj=[min（B）：B∈Pj]，因此Pj决定Hj 。另一方面，N0被定义为H0，而Nj+1=Hj+1\Hj 。 观察到VJ0也由a的长度y确定，而VJj+1由mHj和Nj得到，因此它由yHj和Hj−1确定。根据这些观察结果，得出以下结论现在从一个简单的归纳论证开始。(vi) 设K=Ka<$。 By（v），对于任意k≤K，都有Pa<$，k=P<$b，k和VJa<$，k=V<$Jb，k. 让t，s∈TK，则tA（a<$）=sA（a <$）。定义i=FK（t，ρa<$，K−1）和j=FK（s，ρa<$，K−1）。也定义t=VJa<$，k[i]和s=VaJ<$，k[j]。 这意味着st<$A（a<$）=s<$A（a<$），因为VJa<$，K=V<$Jb，K，我们有tA（<$b） =sA（<$b），这又意味着stA（<$b） =sA（<$b）. 这showsa<$K<$b，soy引理4.1. （ii）wehaveab。QGivenafinitealgebraAanda<$An，定义i Ty pe（a <$）和iUni v（a<$）byiso Type（A，a<$）=（i Ty pe（a <$），iUni v（a<$））。请注意，iUni v（a<$）是一个不涉及Sg（a <$）中所有元素的列表。下一个推论使用刚才介绍的术语总结了引理4 - 2它表明，我们的算法的输出捕获了有限代数结构中元组a的同构。推论4.3LetA是有限代数a。那么对于任何a′，b ′，在以下等同物中：(i) ab(ii) i Ty pe（a<$）=i Ty pe（<$b）。此外，如果这两个条件中的任何一个成立，则映射γ：iUn iv（a<$）[j]→i U n iv（<$b）[j]对于j∈{0，...， |iUni v（a <$）| −1}是从S g（a <$）到S g（<$b）映射a<$的同构B根据引理4.2，如果a b的Pr o。（iii）wehavei Ty pe（a<$）=i Ty pe（<$b）。 相反，如果iType（a <$）=iType（<$b），则有by引理（4.2）。（vi）wehaveab。在任何一种情况下，都有y引理（4.2）。（iii），我们得到Xa<$=X<$b，对于XVJ，P，H，N. 特别地，Ha<$=H<$b，由此可以得出：iUni v（a<$）=iUni v（<$b）。由于iUni v（a<$）中的所有元素（以及iUni v（<$b）中的所有元素）都是不同的，我们知道γ是一个定义明确的双射。此外，由于Pa<$0=P<$b <$0，我们知道γ发送eachaji n到bj。 设t是一项，t是一个同态. 设i∈Ha<$be满足tA（a<$）=Va<$[i]，并定义t=VJa<$[i]。 By（ii），t和t在a<$上一致，因此它们也在<$b上一致。所以我们有一个γ（tA（a<$））=γ（t<$A（a<$））=V<$b[i]=Vj<$b[i]A（<$b），由于VJa<$=V<$J，这等于t<$A（<$b）=tA（<$b）=tA（γ（a<$））。Q5计算QfDefAlg在本节中，我们将介绍我们的算法，以确定有限代数结构中的qf-可定义性该算法基于定理2.1的略微改进，如下文作为推论5.1所述。设a<$=（a1， . ，ak）是元组。 我们定义a′的模式，用模式a′表34M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）23示，为{1，.，n}，使得i，j在同一块中，当且仅当M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2335{{}{}}{⇔⇔⊆∈ai=aj。 例如，模式（a，a，b，c，b，c）=1，2，3，5，4，6。 我们写a′来表示从a′中删除每个等于前一个元素的元素而得到的元组。例如，在一个示例中， [（a，a，b，c，b，c）n=（a，b，c）. 设R是一个关系，θ是一个模式，我们定义：• [R<$：={[a<$$>：a<$∈R}，• s pec（R）：={|[a]|：a<$∈R}，• Rθ：={a<$∈R：patterna<$=θ}Gi venatuplea<$fromAandrelationsR1， . ，RlovererA，令rel Ty pe（a′，R1， . ，Rl）∈{True，False}l是元组（R1（a<$）， . ，Rl（a′））。F或在整数k中的位置，令A（k）：{（a1，.，ak）∈Ak：ai=aj惠i= j}.推论5.1设A是有限代数，R∈Am，设R1，.，Rl是所有形式为[R模式a<$]的关系，其中a<$∈R。以下是等价的：(i) R在A中是qf可定义的。(ii)R1，...，Rl在A中是qf-可定义的。(iii) 对于allk∈spec（R），且对于allab蕴涵rel Ty pe（a<$，R1， . ，R1）=rel Ty pe（<$b，R1， . ，Rl）。证明（i）（ii）之间的等价是一个简单的练习，（ii）（iii）只是定理2.1的重述。Q5.1算法2的分解设A是有限代数，R An. 我们决定R在A中是否是qf可定义的策略可以总结如下。(i) 计算所有形式为[R模式a<$$>的关系，其中a<$∈R。这些是R1，...，Rl(ii) 对于每个k∈spec（R），计算由等价关系导出的划分A（k）.(iii) 如果对某个k∈spec（R），存在ea<$，<$b∈A（k）使得rel Type（a<$，R1， . ，R1）/=rel Ty pe（<$b，R1， . ，Rl）和ab返回False。 否则，返回True。步骤（i）将目标关系分解为没有超复杂信息的关系。这可能会对性能产生严重影响，因为搜索空间以指数方式依赖于目标的arity执行步骤（ii）和（iii）的一个明显的方法是使用函数isoType来用其同构类型标记kspec（R）A（k）中的每个元组，并且每次两个元组具有相同的iType时，检查它们相对于R1具有相同的relType，...，Rl.显然，一旦发现具有相同同构类型的两个元组就执行该测试是方便的，因为如果它失败，算法可以停止（并返回False）。改进第一种方法的另一个观察是，当我们找到具有相同同构的元组a<$，<$b时，我们可以访问（基本上没有任何进一步的计算成本）S g（a <$）和S g（<$b）之间的同构γ b。如果两个元组由yγ连接，则它.36M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）23们具有相同的M. Campercholi et al. /Electronic Notes in Theoretical Computer Science 348（2020）2337∈∈⊆∈∅∈⊆›→||| |同构类型，因此需要计算其中一个的同构类型。这些观察结果以及经过深思熟虑的元组循环策略构成了我们算法背后的主要思想接下来我们将解释它们是如何在执行期间的每一点，存储在轨道k中的数据是A（k）的一个分区，其中每个块都用一些附加信息进行注释。 我们称这些带注释的块为轨道，它们具有（B，RT，T，U）的形式，其中BA（ k ）是实际块，RT是B中所有元组的relType，T将存储B中元组的iType（当已知时），U将存储B中元组的iUniv(when已知）。当算法开始时，每个块都是用其relType注释的单例，T，U被设置为。该算法遍历并处理kspec（R）A（k）中的元组。被遍历的树由A的子宇宙组成，并以A为根。 在一个执行时，该算法通过处理kspec（R）S（k）中的元组来在该树的节点S上工作。为了跟踪当前和以前访问过的节点，以及每个节点上已经处理过的元组，使用了堆栈。堆栈中的条目具有（S，L，G）的形式，其中S是子全域，L是来自S的仍待处理的元组的列表，并且G kspec（R）S（k）是元组的集合，使得：G中的每个元组生成S，并且G中没有两个元组具有相同的同构类型。（跟踪这样一个G的要点将在下面变得清晰堆栈用（A，L0，）初始化，其中L0是kspec（R）A（k）中按arity递增排序的元组的列表。在执行过程中处理的第一个元组是L 0中的第一个元素，每次算法准备好处理一个新元组时，堆栈顶部有一个三元组（S，L，G），L的第一个元素被弹出并处理。 要查看如何处理一个元组，假设stack的顶部是（S，L，G），并且元组a从L中取出。 如果已 知 a的 同 构 （即， 如果a′belongs到一个已知类型的轨道），我们弹出L中的下一个元组（如果L中没有更多的元组，则从堆栈中删除条目（S，L，G））。另一方面，如果a<$的类型未知，则调用函数iso Ty pe来计算它，下一步是搜索c h遍历轨道，看看是否有一个标记为i Ty pe（a <$）。 然而，我们检查哪个轨道（以及之后算法的行为）取决于Sg（a<$）是否比S小。情况S g（a<$）=S。 这里我们只考察G中标记为i Ty pe（a<$）的元组的轨道（为了说明这个曲面，见引理5.3）。 如果这些轨道s中没有一个被标记为i Ty pe（a<$），我们可以使用函数tag_orbit来标记a<$的轨道i T y p e（a <$）和iUni v（a <$），并将a <$添加到G。 另一方面，如果存在一个元素在G中的轨道（B，RT，T，U），其中T=iType（a <$），则，byCorollary4。3、函数γ：iUni v（a<$）[i]U[i]是A的一个次同构。 因此，我们继续合并包含由yγ连接的元组的轨道。特别地，包含a'的轨道被合并，用（B，RT， T， U）表示，husa′在一个用i Ty pe（a′）标记的轨道上结束。的合并由函数try_merge_orbits完成（参见算法3），该函数还检查要合并的任何两个轨道是否具有相同的relType（如果该测试失败，则算法2停止并返回False）。情况|S g（a<$）|<|
我的内容管理
展开
