On the complexity of unification and disunification in commutative idempotent semigroups
Identifieur interne : 000C19 ( PascalFrancis/Checkpoint ); précédent : 000C18; suivant : 000C20On the complexity of unification and disunification in commutative idempotent semigroups
Auteurs : M. Hermann [France] ; P. G. Kolaitis [États-Unis]Source :
- Lecture notes in computer science [ 0302-9743 ] ; 1997.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
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 ACT-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.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:98-0011360Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On the complexity of unification and disunification in commutative idempotent semigroups</title><author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA (CNRS), BP 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation></author><author><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P. G." last="Kolaitis">P. G. Kolaitis</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Computer Science Department, University of California</s1><s2>Santa Cruz, CA 95064</s2><s3>USA</s3><sZ>2 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Santa Cruz, CA 95064</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">98-0011360</idno><date when="1997">1997</date><idno type="stanalyst">PASCAL 98-0011360 INIST</idno><idno type="RBID">Pascal:98-0011360</idno><idno type="wicri:Area/PascalFrancis/Corpus">000C19</idno><idno type="wicri:Area/PascalFrancis/Curation">000C55</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000C19</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000C19</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On the complexity of unification and disunification in commutative idempotent semigroups</title><author><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>LORIA (CNRS), BP 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation></author><author><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P. G." last="Kolaitis">P. G. Kolaitis</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Computer Science Department, University of California</s1><s2>Santa Cruz, CA 95064</s2><s3>USA</s3><sZ>2 aut.</sZ></inist:fA14><country>États-Unis</country><wicri:noRegion>Santa Cruz, CA 95064</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno><imprint><date when="1997">1997</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Lecture notes in computer science</title><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computational complexity</term><term>Computer theory</term><term>Equational theory</term><term>Logical programming</term><term>Unification</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Théorie équationnelle</term><term>Programmation logique</term><term>Unification</term><term>Complexité calcul</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">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 ACT-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><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0></fA01><fA05><s2>1330</s2></fA05><fA08 i1="01" i2="1" l="ENG"><s1>On the complexity of unification and disunification in commutative idempotent semigroups</s1></fA08><fA09 i1="01" i2="1" l="ENG"><s1>Principles and practice of constraint programming - CP 97 : Linz, October 29 - November 1, 1997</s1></fA09><fA11 i1="01" i2="1"><s1>HERMANN (M.)</s1></fA11><fA11 i1="02" i2="1"><s1>KOLAITIS (P. G.)</s1></fA11><fA12 i1="01" i2="1"><s1>SMOLKA (Gert)</s1><s9>ed.</s9></fA12><fA14 i1="01"><s1>LORIA (CNRS), BP 239</s1><s2>54506 Vandœuvre-lès-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA14 i1="02"><s1>Computer Science Department, University of California</s1><s2>Santa Cruz, CA 95064</s2><s3>USA</s3><sZ>2 aut.</sZ></fA14><fA20><s1>282-296</s1></fA20><fA21><s1>1997</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA26 i1="01"><s0>3-540-63753-2</s0></fA26><fA43 i1="01"><s1>INIST</s1><s2>16343</s2><s5>354000068105770210</s5></fA43><fA44><s0>0000</s0><s1>© 1997 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>20 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>98-0011360</s0></fA47><fA60><s1>P</s1><s2>C</s2></fA60><fA61><s0>A</s0></fA61><fA64 i2="1"><s0>Lecture notes in computer science</s0></fA64><fA66 i1="01"><s0>DEU</s0></fA66><fA66 i1="02"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>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 ACT-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.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02A07</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Informatique théorique</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Computer theory</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Informática teórica</s0><s5>01</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Théorie équationnelle</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Equational theory</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Teoría ecuaciónal</s0><s5>02</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Programmation logique</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Logical programming</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Programación lógica</s0><s5>03</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Unification</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Unification</s0><s5>04</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Unificación</s0><s5>04</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Complexité calcul</s0><s5>05</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Computational complexity</s0><s5>05</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Complejidad computación</s0><s5>05</s5></fC03><fN21><s1>364</s1></fN21></pA><pR><fA30 i1="01" i2="1" l="ENG"><s1>International conference on principles and practice of constraint programming</s1><s2>3</s2><s3>Schloss Hagenberg AUT</s3><s4>1997-10-29</s4></fA30></pR></standard></inist><affiliations><list><country><li>France</li><li>États-Unis</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Vandœuvre-lès-Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Hermann, M" sort="Hermann, M" uniqKey="Hermann M" first="M." last="Hermann">M. Hermann</name></region></country><country name="États-Unis"><noRegion><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P. G." last="Kolaitis">P. G. Kolaitis</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C19 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000C19 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:98-0011360
|texte= On the complexity of unification and disunification in commutative idempotent semigroups
}}
| This area was generated with Dilib version V0.6.33. |  |