Computational complexity of simultaneous elementary matching problems
Identifieur interne : 000C50 ( Istex/Corpus ); précédent : 000C49; suivant : 000C51Computational complexity of simultaneous elementary matching problems
Auteurs : Miki Hermann ; Phokion G. KolaitisSource :
- 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 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><affiliation><mods:affiliation>CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506, Vand∄uvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hermann@loria.fr</mods:affiliation></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><mods:affiliation>Computer and Information Sciences, University of California, 95064, Santa Cruz, CA, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: kolaitis@cse.ucsc.edu</mods:affiliation></affiliation></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></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><mods:affiliation>CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506, Vand∄uvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hermann@loria.fr</mods:affiliation></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><mods:affiliation>Computer and Information Sciences, University of California, 95064, Santa Cruz, CA, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: kolaitis@cse.ucsc.edu</mods:affiliation></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><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Miki Hermann</name><affiliations><json:string>CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506, Vand∄uvre-lès-Nancy, France</json:string><json:string>E-mail: hermann@loria.fr</json:string></affiliations></json:item><json:item><name>Phokion G. Kolaitis</name><affiliations><json:string>Computer and Information Sciences, University of California, 95064, Santa Cruz, CA, USA</json:string><json:string>E-mail: kolaitis@cse.ucsc.edu</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-GVNRP01W-C</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><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.</abstract><qualityIndicators><score>8.992</score><pdfWordCount>5888</pdfWordCount><pdfCharCount>33345</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>12</pdfPageCount><pdfPageSize>439.28 x 662.28 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>166</abstractWordCount><abstractCharCount>1107</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Computational complexity of simultaneous elementary matching problems</title><chapterId><json:string>34</json:string><json:string>Chap34</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>1995</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item><json:item><name>Jan van Leeuwen</name></json:item></editor></serie><host><title>Mathematical Foundations of Computer Science 1995</title><language><json:string>unknown</json:string></language><copyrightDate>1995</copyrightDate><doi><json:string>10.1007/3-540-60246-1</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-44768-9</json:string></eisbn><bookId><json:string>3540602461</json:string></bookId><isbn><json:string>978-3-540-60246-0</json:string></isbn><volume>969</volume><pages><first>359</first><last>370</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Jiří Wiedermann</name></json:item><json:item><name>Petr Hájek</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Programming Languages, Compilers, Interpreters</value></json:item><json:item><value>Software Engineering</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-GVNRP01W-C</json:string></ark><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1007/3-540-60246-1_142</json:string></doi><id>350D861638085017A62974FB39B5584E9884C8CC</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Computational complexity of simultaneous elementary matching problems</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag</licence></availability><date when="1995">1995</date></publicationStmt><notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Computational complexity of simultaneous elementary matching problems</title><author><persName><forename type="first">Miki</forename><surname>Hermann</surname></persName><email>hermann@loria.fr</email><affiliation><orgName type="institution">CRIN (CNRS) and INRIA-Lorraine</orgName><address><postBox>BP 239</postBox><postCode>54506</postCode><settlement>Vand∄uvre-lès-Nancy</settlement><country key="FR">FRANCE</country></address></affiliation></author><author><persName><forename type="first">Phokion</forename><forename type="first">G.</forename><surname>Kolaitis</surname></persName><email>kolaitis@cse.ucsc.edu</email><affiliation><orgName type="department">Computer and Information Sciences</orgName><orgName type="institution">University of California</orgName><address><postCode>95064</postCode><settlement>Santa Cruz</settlement><region>CA</region><country key="US">UNITED STATES</country></address></affiliation></author><idno type="istex">350D861638085017A62974FB39B5584E9884C8CC</idno><idno type="ark">ark:/67375/HCB-GVNRP01W-C</idno><idno type="DOI">10.1007/3-540-60246-1_142</idno></analytic><monogr><title level="m" type="main">Mathematical Foundations of Computer Science 1995</title><title level="m" type="sub">20th International Symposium, MFCS '95 Prague, Czech Republic, August 28–September 1, 1995 Proceedings</title><idno type="DOI">10.1007/3-540-60246-1</idno><idno type="book-id">3540602461</idno><idno type="ISBN">978-3-540-60246-0</idno><idno type="eISBN">978-3-540-44768-9</idno><idno type="chapter-id">Chap34</idno><editor><persName><forename type="first">Jiří</forename><surname>Wiedermann</surname></persName></editor><editor><persName><forename type="first">Petr</forename><surname>Hájek</surname></persName></editor><imprint><biblScope unit="vol">969</biblScope><biblScope unit="page" from="359">359</biblScope><biblScope unit="page" to="370">370</biblScope><biblScope unit="chapter-count">54</biblScope></imprint></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><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">Jan</forename><nameLink>van</nameLink><surname>Leeuwen</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>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.</p></abstract><textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label><item><term type="Primary">Computer Science</term></item><label>I16013</label><item><term type="Secondary" subtype="priority-1">Computation by Abstract Devices</term></item><label>I16021</label><item><term type="Secondary" subtype="priority-2">Algorithm Analysis and Problem Complexity</term></item><label>I1603X</label><item><term type="Secondary" subtype="priority-3">Logics and Meanings of Programs</term></item><label>I16048</label><item><term type="Secondary" subtype="priority-4">Mathematical Logic and Formal Languages</term></item><label>I14037</label><item><term type="Secondary" subtype="priority-5">Programming Languages, Compilers, Interpreters</term></item><label>I14029</label><item><term type="Secondary" subtype="priority-6">Software Engineering</term></item></list></keywords></textClass><langUsage><language ident="EN"></language></langUsage></profileDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540602461</BookID><BookTitle>Mathematical Foundations of Computer Science 1995</BookTitle><BookSubTitle>20th International Symposium, MFCS '95 Prague, Czech Republic, August 28–September 1, 1995 Proceedings</BookSubTitle><BookVolumeNumber>969</BookVolumeNumber><BookDOI>10.1007/3-540-60246-1</BookDOI><BookTitleID>42638</BookTitleID><BookPrintISBN>978-3-540-60246-0</BookPrintISBN><BookElectronicISBN>978-3-540-44768-9</BookElectronicISBN><BookChapterCount>54</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16013" Priority="1" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I16021" Priority="2" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I1603X" Priority="3" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16048" Priority="4" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I14037" Priority="5" Type="Secondary">Programming Languages, Compilers, Interpreters</BookSubject><BookSubject Code="I14029" Priority="6" Type="Secondary">Software Engineering</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Jiří</GivenName><FamilyName>Wiedermann</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Petr</GivenName><FamilyName>Hájek</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap34" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>34</ChapterID><ChapterDOI>10.1007/3-540-60246-1_142</ChapterDOI><ChapterSequenceNumber>34</ChapterSequenceNumber><ChapterTitle Language="En">Computational complexity of simultaneous elementary matching problems</ChapterTitle><ChapterSubTitle Language="En">Extended abstract</ChapterSubTitle><ChapterCategory>Contributed Papers</ChapterCategory><ChapterSubCategory>Unification, Rewriting, Type Theory</ChapterSubCategory><ChapterFirstPage>359</ChapterFirstPage><ChapterLastPage>370</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1995</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>2</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540602461</BookID><BookTitle>Mathematical Foundations of Computer Science 1995</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Miki</GivenName><FamilyName>Hermann</FamilyName></AuthorName><Contact><Email>hermann@loria.fr</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Phokion</GivenName><GivenName>G.</GivenName><FamilyName>Kolaitis</FamilyName></AuthorName><Contact><Email>kolaitis@cse.ucsc.edu</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>CRIN (CNRS) and INRIA-Lorraine</OrgName><OrgAddress><Postbox>BP 239</Postbox><Postcode>54506</Postcode><City>Vand∄uvre-lès-Nancy</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Computer and Information Sciences</OrgDivision><OrgName>University of California</OrgName><OrgAddress><Postcode>95064</Postcode><City>Santa Cruz</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>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.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>Partially supported by a NATO grant. Research was carried out while this author was visiting the University of California, Santa Cruz.</SimplePara></ArticleNote><ArticleNote Type="Misc"><SimplePara>Partially supported by a Guggenheim Fellowhsip and NSF Grant CCR-9307758.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Computational complexity of simultaneous elementary matching problems</title><subTitle>Extended abstract</subTitle></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Computational complexity of simultaneous elementary matching problems</title></titleInfo><name type="personal"><namePart type="given">Miki</namePart><namePart type="family">Hermann</namePart><affiliation>CRIN (CNRS) and INRIA-Lorraine, BP 239, 54506, Vand∄uvre-lès-Nancy, France</affiliation><affiliation>E-mail: hermann@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Phokion</namePart><namePart type="given">G.</namePart><namePart type="family">Kolaitis</namePart><affiliation>Computer and Information Sciences, University of California, 95064, Santa Cruz, CA, USA</affiliation><affiliation>E-mail: kolaitis@cse.ucsc.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="ReviewPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">1995</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract 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.</abstract><relatedItem type="host"><titleInfo><title>Mathematical Foundations of Computer Science 1995</title><subTitle>20th International Symposium, MFCS '95 Prague, Czech Republic, August 28–September 1, 1995 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Jiří</namePart><namePart type="family">Wiedermann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Petr</namePart><namePart type="family">Hájek</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1995</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I14037">Programming Languages, Compilers, Interpreters</topic><topic authority="SpringerSubjectCodes" authorityURI="I14029">Software Engineering</topic></subject><identifier type="DOI">10.1007/3-540-60246-1</identifier><identifier type="ISBN">978-3-540-60246-0</identifier><identifier type="eISBN">978-3-540-44768-9</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">42638</identifier><identifier type="BookID">3540602461</identifier><identifier type="BookChapterCount">54</identifier><identifier type="BookVolumeNumber">969</identifier><part><date>1995</date><detail type="volume"><number>969</number><caption>vol.</caption></detail><extent unit="pages"><start>359</start><end>370</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1995</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></relatedItem><identifier type="istex">350D861638085017A62974FB39B5584E9884C8CC</identifier><identifier type="ark">ark:/67375/HCB-GVNRP01W-C</identifier><identifier type="DOI">10.1007/3-540-60246-1_142</identifier><identifier type="ChapterID">34</identifier><identifier type="ChapterID">Chap34</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1995</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource><recordOrigin>Springer-Verlag, 1995</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-GVNRP01W-C/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C50 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000C50 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:350D861638085017A62974FB39B5584E9884C8CC
|texte= Computational complexity of simultaneous elementary matching problems
}}
| This area was generated with Dilib version V0.6.33. |  |