The Complexity of Counting Problems in Equational Matching
Identifieur interne : 002B44 ( Crin/Checkpoint ); précédent : 002B43; suivant : 002B45The Complexity of Counting Problems in Equational Matching
Auteurs : N. Hermann ; P.-G. KolaitisSource :
- Journal of Symbolic Computation ; 1995.
Abstract
We introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If~E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does. In 1979, L.\ Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-{\em complete\/} problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories~E. We establish that if E is one of the equational theories~A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete.
Links toward previous steps (curation, corpus...)
Links to Exploration step
CRIN:hermann96cLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="506">The Complexity of Counting Problems in Equational Matching</title></titleStmt><publicationStmt><idno type="RBID">CRIN:hermann96c</idno><date when="1995" year="1995">1995</date><idno type="wicri:Area/Crin/Corpus">001746</idno><idno type="wicri:Area/Crin/Curation">001746</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">001746</idno><idno type="wicri:Area/Crin/Checkpoint">002B44</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002B44</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">The Complexity of Counting Problems in Equational Matching</title><author><name sortKey="Hermann, N" sort="Hermann, N" uniqKey="Hermann N" first="N." last="Hermann">N. Hermann</name></author><author><name sortKey="Kolaitis, P G" sort="Kolaitis, P G" uniqKey="Kolaitis P" first="P.-G." last="Kolaitis">P.-G. Kolaitis</name></author></analytic><series><title level="j">Journal of Symbolic Computation</title><imprint><date when="1995" type="published">1995</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="5964">We introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If~E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does. In 1979, L.\ Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-{\em complete\/} problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories~E. We establish that if E is one of the equational theories~A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete.</div></front></TEI><BibTex type="article"><ref>hermann96c</ref><crinnumber>96-R-057</crinnumber><category>1</category><equipe>EURECA</equipe><author><e>Hermann, N.</e><e>Kolaitis, P.-G.</e></author><title>The Complexity of Counting Problems in Equational Matching</title><journal>Journal of Symbolic Computation</journal><year>1995</year><volume>20</volume><number>3</number><pages>343-362</pages><month>Sep</month><note>L'article et le numéro de la revue sont parus effectivement en avril 1996 mais antidatés par l'éditeur</note><abstract>We introduce a class of counting problems that arise naturally in equational matching and investigate their computational complexity. If~E is an equational theory, then #E-Matching is the problem of counting the number of most general E-matchers of two given terms. #E-Matching is a well-defined algorithmic problem for every finitary equational theory. Moreover, it captures more accurately the computational difficulties associated with finding minimal complete sets of E-matchers than the corresponding decision problem for E-matching does. In 1979, L.\ Valiant developed a computational model for measuring the complexity of counting problems and demonstrated the existence of #P-{\em complete\/} problems, i.e., counting problems that are complete for counting non-deterministic Turing machines of polynomial-time complexity. Using the theory of #P-completeness, we analyze the computational complexity of #E-matching for several important equational theories~E. We establish that if E is one of the equational theories~A, C, AC, I, U, ACI, Set, ACU, or ACIU, then #E-Matching is a #P-complete problem. We also show that there are equational theories, such as the restriction of AC-matching to linear terms, for which the underlying decision matching problem is solvable in polynomial time, while the associated counting matching problem is #P-complete.</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 002B44 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Crin/Checkpoint/biblio.hfd -nk 002B44 | 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:hermann96c
|texte= The Complexity of Counting Problems in Equational Matching
}}
| This area was generated with Dilib version V0.6.33. |  |