Computational complexity of simultaneous elementary matching problems
Identifieur interne : 00D031 ( Main/Merge ); précédent : 00D030; suivant : 00D032Computational 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
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
Links to Exploration step
ISTEX:350D861638085017A62974FB39B5584E9884C8CCLe 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></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></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00D031 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00D031 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:350D861638085017A62974FB39B5584E9884C8CC
|texte= Computational complexity of simultaneous elementary matching problems
}}
| This area was generated with Dilib version V0.6.33. |  |