Closure of Hedge-Automata Languages by Hedge Rewriting
Identifieur interne : 000557 ( Istex/Corpus ); précédent : 000556; suivant : 000558Closure of Hedge-Automata Languages by Hedge Rewriting
Auteurs : Florent Jacquemard ; Michael RusinowitchSource :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages. In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.
Url:
DOI: 10.1007/978-3-540-70590-1_11
Links to Exploration step
ISTEX:18FF5A31AF63D0682416068893FC83F2BE06511BLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Closure of Hedge-Automata Languages by Hedge Rewriting</title><author><name sortKey="Jacquemard, Florent" sort="Jacquemard, Florent" uniqKey="Jacquemard F" first="Florent" last="Jacquemard">Florent Jacquemard</name><affiliation><mods:affiliation>INRIA Futurs and LSV, UMR CNRS, ENS Cachan, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: florent.jacquemard@lsv.ens-cachan.fr</mods:affiliation></affiliation></author><author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name><affiliation><mods:affiliation>LORIA & INRIA Lorraine, UMR 7503, </mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rusi@loria.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:18FF5A31AF63D0682416068893FC83F2BE06511B</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-70590-1_11</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-N0JL3DLT-8/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000557</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000557</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Closure of Hedge-Automata Languages by Hedge Rewriting</title><author><name sortKey="Jacquemard, Florent" sort="Jacquemard, Florent" uniqKey="Jacquemard F" first="Florent" last="Jacquemard">Florent Jacquemard</name><affiliation><mods:affiliation>INRIA Futurs and LSV, UMR CNRS, ENS Cachan, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: florent.jacquemard@lsv.ens-cachan.fr</mods:affiliation></affiliation></author><author><name sortKey="Rusinowitch, Michael" sort="Rusinowitch, Michael" uniqKey="Rusinowitch M" first="Michael" last="Rusinowitch">Michael Rusinowitch</name><affiliation><mods:affiliation>LORIA & INRIA Lorraine, UMR 7503, </mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: rusi@loria.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</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: We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages. In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.</div></front></TEI><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Florent Jacquemard</name><affiliations><json:string>INRIA Futurs and LSV, UMR CNRS, ENS Cachan, France</json:string><json:string>E-mail: florent.jacquemard@lsv.ens-cachan.fr</json:string></affiliations></json:item><json:item><name>Michael Rusinowitch</name><affiliations><json:string>LORIA & INRIA Lorraine, UMR 7503,</json:string><json:string>E-mail: rusi@loria.fr</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-N0JL3DLT-8</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages. In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.</abstract><qualityIndicators><score>9.592</score><pdfWordCount>7595</pdfWordCount><pdfCharCount>34509</pdfCharCount><pdfVersion>1.6</pdfVersion><pdfPageCount>15</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>216</abstractWordCount><abstractCharCount>1424</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Closure of Hedge-Automata Languages by Hedge Rewriting</title><chapterId><json:string>11</json:string><json:string>Chap11</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>2008</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>David Hutchison</name></json:item><json:item><name>Takeo Kanade</name></json:item><json:item><name>Josef Kittler</name></json:item><json:item><name>Jon M. Kleinberg</name></json:item><json:item><name>Friedemann Mattern</name></json:item><json:item><name>John C. Mitchell</name></json:item><json:item><name>Moni Naor</name></json:item><json:item><name>Oscar Nierstrasz</name></json:item><json:item><name>C. Pandu Rangan</name></json:item><json:item><name>Bernhard Steffen</name></json:item><json:item><name>Madhu Sudan</name></json:item><json:item><name>Demetri Terzopoulos</name></json:item><json:item><name>Doug Tygar</name></json:item><json:item><name>Moshe Y. Vardi</name></json:item><json:item><name>Gerhard Weikum</name></json:item></editor></serie><host><title>Rewriting Techniques and Applications</title><language><json:string>unknown</json:string></language><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-70590-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-70590-1</json:string></eisbn><bookId><json:string>978-3-540-70590-1</json:string></bookId><isbn><json:string>978-3-540-70588-8</json:string></isbn><volume>5117</volume><pages><first>157</first><last>171</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Andrei Voronkov</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Programming Languages, Compilers, Interpreters</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Symbolic and Algebraic Manipulation</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-N0JL3DLT-8</json:string></ark><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-70590-1_11</json:string></doi><id>18FF5A31AF63D0682416068893FC83F2BE06511B</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-N0JL3DLT-8/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-N0JL3DLT-8/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-N0JL3DLT-8/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Closure of Hedge-Automata Languages by Hedge Rewriting</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="2008">2008</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">Closure of Hedge-Automata Languages by Hedge Rewriting</title><author><persName><forename type="first">Florent</forename><surname>Jacquemard</surname></persName><email>florent.jacquemard@lsv.ens-cachan.fr</email><affiliation><orgName type="institution">INRIA Futurs and LSV, UMR CNRS, ENS Cachan</orgName><address><country key="FR">FRANCE</country></address></affiliation></author><author><persName><forename type="first">Michael</forename><surname>Rusinowitch</surname></persName><email>rusi@loria.fr</email><affiliation><orgName type="institution">LORIA & INRIA Lorraine, UMR 7503</orgName><address><country key=""></country></address></affiliation></author><idno type="istex">18FF5A31AF63D0682416068893FC83F2BE06511B</idno><idno type="ark">ark:/67375/HCB-N0JL3DLT-8</idno><idno type="DOI">10.1007/978-3-540-70590-1_11</idno></analytic><monogr><title level="m" type="main">Rewriting Techniques and Applications</title><title level="m" type="sub">19th International Conference, RTA 2008 Hagenberg, Austria, July 15-17, 2008 Proceedings</title><idno type="DOI">10.1007/978-3-540-70590-1</idno><idno type="book-id">978-3-540-70590-1</idno><idno type="ISBN">978-3-540-70588-8</idno><idno type="eISBN">978-3-540-70590-1</idno><idno type="chapter-id">Chap11</idno><editor><persName><forename type="first">Andrei</forename><surname>Voronkov</surname></persName><email>voronkov@cs.manchester.ac.uk</email></editor><imprint><biblScope unit="vol">5117</biblScope><biblScope unit="page" from="157">157</biblScope><biblScope unit="page" to="171">171</biblScope><biblScope unit="chapter-count">30</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</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>We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting.</p><p>We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages.</p><p>In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.</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>I16048</label><item><term type="Secondary" subtype="priority-1">Mathematical Logic and Formal Languages</term></item><label>I1603X</label><item><term type="Secondary" subtype="priority-2">Logics and Meanings of Programs</term></item><label>I14037</label><item><term type="Secondary" subtype="priority-3">Programming Languages, Compilers, Interpreters</term></item><label>I21017</label><item><term type="Secondary" subtype="priority-4">Artificial Intelligence (incl. Robotics)</term></item><label>I17052</label><item><term type="Secondary" subtype="priority-5">Symbolic and Algebraic Manipulation</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-N0JL3DLT-8/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 SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-70590-1</BookID><BookTitle>Rewriting Techniques and Applications</BookTitle><BookSubTitle>19th International Conference, RTA 2008 Hagenberg, Austria, July 15-17, 2008 Proceedings</BookSubTitle><BookVolumeNumber>5117</BookVolumeNumber><BookSequenceNumber>5117</BookSequenceNumber><BookDOI>10.1007/978-3-540-70590-1</BookDOI><BookTitleID>164833</BookTitleID><BookPrintISBN>978-3-540-70588-8</BookPrintISBN><BookElectronicISBN>978-3-540-70590-1</BookElectronicISBN><BookChapterCount>30</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16048" Priority="1" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I1603X" Priority="2" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I14037" Priority="3" Type="Secondary">Programming Languages, Compilers, Interpreters</BookSubject><BookSubject Code="I21017" Priority="4" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I17052" Priority="5" Type="Secondary">Symbolic and Algebraic Manipulation</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Andrei</GivenName><FamilyName>Voronkov</FamilyName></EditorName><Contact><Email>voronkov@cs.manchester.ac.uk</Email></Contact></Editor></EditorGroup></BookHeader><Chapter ID="Chap11" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>11</ChapterID><ChapterDOI>10.1007/978-3-540-70590-1_11</ChapterDOI><ChapterSequenceNumber>11</ChapterSequenceNumber><ChapterTitle Language="En">Closure of Hedge-Automata Languages by Hedge Rewriting</ChapterTitle><ChapterFirstPage>157</ChapterFirstPage><ChapterLastPage>171</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></ChapterCopyright><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>978-3-540-70590-1</BookID><BookTitle>Rewriting Techniques and Applications</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Florent</GivenName><FamilyName>Jacquemard</FamilyName></AuthorName><Contact><Email>florent.jacquemard@lsv.ens-cachan.fr</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Michael</GivenName><FamilyName>Rusinowitch</FamilyName></AuthorName><Contact><Email>rusi@loria.fr</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>INRIA Futurs and LSV, UMR CNRS, ENS Cachan</OrgName><OrgAddress><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>LORIA & INRIA Lorraine, UMR 7503</OrgName><OrgAddress><Country> </Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting.</Para><Para>We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages.</Para><Para>In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Closure of Hedge-Automata Languages by Hedge Rewriting</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Closure of Hedge-Automata Languages by Hedge Rewriting</title></titleInfo><name type="personal"><namePart type="given">Florent</namePart><namePart type="family">Jacquemard</namePart><affiliation>INRIA Futurs and LSV, UMR CNRS, ENS Cachan, France</affiliation><affiliation>E-mail: florent.jacquemard@lsv.ens-cachan.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Michael</namePart><namePart type="family">Rusinowitch</namePart><affiliation>LORIA & INRIA Lorraine, UMR 7503, </affiliation><affiliation>E-mail: rusi@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" 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">2008</dateIssued><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: We consider rewriting systems for unranked ordered terms, i.e. trees where the number of successors of a node is not determined by its label, and is not a priori bounded. The rewriting systems are defined such that variables in the rewrite rules can be substituted by hedges (sequences of terms) instead of just terms. Consequently, this notion of rewriting subsumes both standard term rewriting and word rewriting. We investigate some preservation properties for two classes of languages of unranked ordered terms under this generalization of term rewriting. The considered classes include languages of hedge automata (HA) and some extension (called CF-HA) with context-free languages in transitions, instead of regular languages. In particular, we show that the set of unranked terms reachable from a given HA language, using a so called inverse context-free rewrite system, is a HA language. The proof, based on a HA completion procedure, reuses and combines known techniques with non-trivial adaptations. Moreover, we prove, with different techniques, that the closure of CF-HA languages with respect to restricted context-free rewrite systems, the symmetric case of the above rewrite systems, is a CF-HA language. As a consequence, the problems of ground reachability and regular hedge model checking are decidable in both cases. We give several counter examples showing that we cannot relax the restrictions.</abstract><relatedItem type="host"><titleInfo><title>Rewriting Techniques and Applications</title><subTitle>19th International Conference, RTA 2008 Hagenberg, Austria, July 15-17, 2008 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Andrei</namePart><namePart type="family">Voronkov</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">2008</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="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I14037">Programming Languages, Compilers, Interpreters</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I17052">Symbolic and Algebraic Manipulation</topic></subject><identifier type="DOI">10.1007/978-3-540-70590-1</identifier><identifier type="ISBN">978-3-540-70588-8</identifier><identifier type="eISBN">978-3-540-70590-1</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">164833</identifier><identifier type="BookID">978-3-540-70590-1</identifier><identifier type="BookChapterCount">30</identifier><identifier type="BookVolumeNumber">5117</identifier><identifier type="BookSequenceNumber">5117</identifier><part><date>2008</date><detail type="volume"><number>5117</number><caption>vol.</caption></detail><extent unit="pages"><start>157</start><end>171</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2008</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 Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><identifier type="istex">18FF5A31AF63D0682416068893FC83F2BE06511B</identifier><identifier type="ark">ark:/67375/HCB-N0JL3DLT-8</identifier><identifier type="DOI">10.1007/978-3-540-70590-1_11</identifier><identifier type="ChapterID">11</identifier><identifier type="ChapterID">Chap11</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2008</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 Berlin Heidelberg, 2008</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-N0JL3DLT-8/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 000557 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000557 | 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:18FF5A31AF63D0682416068893FC83F2BE06511B
|texte= Closure of Hedge-Automata Languages by Hedge Rewriting
}}
| This area was generated with Dilib version V0.6.33. |  |