Computational complexity of simultaneous elementary matching problems
Identifieur interne : 00C774 ( Main/Exploration ); précédent : 00C773; suivant : 00C775Computational complexity of simultaneous elementary matching problems
Auteurs : Miki Hermann [France] ; Phokion G. Kolaitis [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The simultaneous elementary E-matching problem for an equational theory E is to decide whether there is an E-matcher for a given system of equations in which the only function symbols occurring in the terms to be matched are the ones constrained by the equational axioms of E. We study the computational complexity of simultaneous elementary matching problems for the equational theories A of semigroups, AC of commutative semigroups, and ACU of commutative monoids. In each case, we delineate the boundary between NP-completeness and solvability in polynomial time by considering two parameters, the number of equations in the systems and the number of constant symbols in the signature. Moreover, we analyze further the intractable cases of simultaneous elementary AC-matching and ACU-matching by taking also into account the maximum number of occurrences of each variable. Using graph-theoretic techniques, we show that if each variable is restricted to having at most two occurrences, then several cases of simultaneous elementary AC-matching and ACU-matching can be solved in polynomial time.
Url:
DOI: 10.1007/3-540-60246-1_142
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000C50
- to stream Istex, to step Curation: 000C42
- to stream Istex, to step Checkpoint: 002B89
- to stream Main, to step Merge: 00D031
- to stream Main, to step Curation: 00C774
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Computational complexity of simultaneous elementary matching problems</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>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:350D861638085017A62974FB39B5584E9884C8CC</idno>
<date when="1995" year="1995">1995</date>
<idno type="doi">10.1007/3-540-60246-1_142</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000C50</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C50</idno>
<idno type="wicri:Area/Istex/Curation">000C42</idno>
<idno type="wicri:Area/Istex/Checkpoint">002B89</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002B89</idno>
<idno type="wicri:doubleKey">0302-9743:1995:Hermann M:computational:complexity:of</idno>
<idno type="wicri:Area/Main/Merge">00D031</idno>
<idno type="wicri:Area/Main/Curation">00C774</idno>
<idno type="wicri:Area/Main/Exploration">00C774</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Computational complexity of simultaneous elementary matching problems</title>
<author><name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506, Vand∄uvre-lès-Nancy</wicri:regionArea>
<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>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Computer and Information Sciences, University of California, 95064, Santa Cruz, CA</wicri:regionArea>
<placeName><region type="state">Californie</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<title level="s" type="abbrev">Lect Notes Comput Sci</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The simultaneous elementary E-matching problem for an equational theory E is to decide whether there is an E-matcher for a given system of equations in which the only function symbols occurring in the terms to be matched are the ones constrained by the equational axioms of E. We study the computational complexity of simultaneous elementary matching problems for the equational theories A of semigroups, AC of commutative semigroups, and ACU of commutative monoids. In each case, we delineate the boundary between NP-completeness and solvability in polynomial time by considering two parameters, the number of equations in the systems and the number of constant symbols in the signature. Moreover, we analyze further the intractable cases of simultaneous elementary AC-matching and ACU-matching by taking also into account the maximum number of occurrences of each variable. Using graph-theoretic techniques, we show that if each variable is restricted to having at most two occurrences, then several cases of simultaneous elementary AC-matching and ACU-matching can be solved in polynomial time.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
<region><li>Californie</li>
<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, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
</region>
<name sortKey="Hermann, Miki" sort="Hermann, Miki" uniqKey="Hermann M" first="Miki" last="Hermann">Miki Hermann</name>
</country>
<country name="États-Unis"><region name="Californie"><name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
</region>
<name sortKey="Kolaitis, Phokion G" sort="Kolaitis, Phokion G" uniqKey="Kolaitis P" first="Phokion G." last="Kolaitis">Phokion G. Kolaitis</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00C774 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00C774 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:350D861638085017A62974FB39B5584E9884C8CC |texte= Computational complexity of simultaneous elementary matching problems }}
This area was generated with Dilib version V0.6.33. |