On the complexity of unification and disunification in commutative idempotent semigroups
Identifieur interne : 002606 ( Crin/Checkpoint ); précédent : 002605; suivant : 002607On the complexity of unification and disunification in commutative idempotent semigroups
Auteurs : Miki Hermann ; Phokion G. KolaitisSource :
English descriptors
Abstract
We analyze the computational complexity of elementary unification and disunification problems for the equational theory ACI of commutative idempotent semigroups. From earlier work, it was known that the decision problem for elementary ACI-unification is solvable in polynomial time. We show that this problem is inherently sequential by establishing that it is complete for polynomial time (P-complete) via logarithmic-space reductions. We also investigate the decision problem and the counting problem for elementary ACI-matching and observe that the former is solvable in logarithmic space, but the latter is #P-complete. After this, we analyze the computational complexity of the decision problem for elementary ground ACI-disunification. Finally, we study the computational complexity of a restricted version of elementary ACI-matching, which arises naturally as a set-term matching problem in the context of the logic data language LDL. In both cases, we delineate the boundary between polynomial-time solvability and NP-hardness by taking into account two parameters, the number of free constants and the number of disequations or equations.
Links toward previous steps (curation, corpus...)
Links to Exploration step
CRIN:hermann97aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="625">On the complexity of unification and disunification in commutative idempotent semigroups</title></titleStmt><publicationStmt><idno type="RBID">CRIN:hermann97a</idno><date when="1997" year="1997">1997</date><idno type="wicri:Area/Crin/Corpus">001F05</idno><idno type="wicri:Area/Crin/Curation">001F05</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">001F05</idno><idno type="wicri:Area/Crin/Checkpoint">002606</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002606</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On the complexity of unification and disunification in commutative idempotent semigroups</title><author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name></author><author><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>commutative idempotent semigroups</term><term>complexity</term><term>disunification</term><term>unification</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="5048">We analyze the computational complexity of elementary unification and disunification problems for the equational theory ACI of commutative idempotent semigroups. From earlier work, it was known that the decision problem for elementary ACI-unification is solvable in polynomial time. We show that this problem is inherently sequential by establishing that it is complete for polynomial time (P-complete) via logarithmic-space reductions. We also investigate the decision problem and the counting problem for elementary ACI-matching and observe that the former is solvable in logarithmic space, but the latter is #P-complete. After this, we analyze the computational complexity of the decision problem for elementary ground ACI-disunification. Finally, we study the computational complexity of a restricted version of elementary ACI-matching, which arises naturally as a set-term matching problem in the context of the logic data language LDL. In both cases, we delineate the boundary between polynomial-time solvability and NP-hardness by taking into account two parameters, the number of free constants and the number of disequations or equations.</div></front></TEI><BibTex type="inproceedings"><ref>hermann97a</ref><crinnumber>97-R-205</crinnumber><category>3</category><equipe>PROTHEO</equipe><author><e>Hermann, Miki</e><e>Kolaitis, Phokion G.</e></author><title>On the complexity of unification and disunification in commutative idempotent semigroups</title><booktitle>{3rd International Conference on Principles and Practice of Constraint Programming (CP'97), Linz, Autriche}</booktitle><year>1997</year><volume>1330</volume><series>Lecture Notes in Computer Science</series><pages>282-296</pages><month>oct</month><publisher>Springer-Verlag</publisher><keywords><e>unification</e><e>disunification</e><e>complexity</e><e>commutative idempotent semigroups</e></keywords><abstract>We analyze the computational complexity of elementary unification and disunification problems for the equational theory ACI of commutative idempotent semigroups. From earlier work, it was known that the decision problem for elementary ACI-unification is solvable in polynomial time. We show that this problem is inherently sequential by establishing that it is complete for polynomial time (P-complete) via logarithmic-space reductions. We also investigate the decision problem and the counting problem for elementary ACI-matching and observe that the former is solvable in logarithmic space, but the latter is #P-complete. After this, we analyze the computational complexity of the decision problem for elementary ground ACI-disunification. Finally, we study the computational complexity of a restricted version of elementary ACI-matching, which arises naturally as a set-term matching problem in the context of the logic data language LDL. In both cases, we delineate the boundary between polynomial-time solvability and NP-hardness by taking into account two parameters, the number of free constants and the number of disequations or equations.</abstract></BibTex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Crin/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002606 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Checkpoint/biblio.hfd -nk 002606 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Crin
|étape= Checkpoint
|type= RBID
|clé= CRIN:hermann97a
|texte= On the complexity of unification and disunification in commutative idempotent semigroups
}}
| This area was generated with Dilib version V0.6.33. |  |