Partition-Refining Algorithms for Learning Finite State Automata
Identifieur interne : 000E33 ( Istex/Corpus ); précédent : 000E32; suivant : 000E34Partition-Refining Algorithms for Learning Finite State Automata
Auteurs : Tapio ElomaaSource :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence. In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language. We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of k-reversible languages. Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.
Url:
DOI: 10.1007/3-540-48050-1_27
Links to Exploration step
ISTEX:375432E5DF16E7B007EE5410D404654EEA80F719Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Partition-Refining Algorithms for Learning Finite State Automata</title><author><name sortKey="Elomaa, Tapio" sort="Elomaa, Tapio" uniqKey="Elomaa T" first="Tapio" last="Elomaa">Tapio Elomaa</name><affiliation><mods:affiliation>Department of Computer Science, University of Helsinki, Teollisuuskatu 23, P. O. Box 26, FIN-00014, Finland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: elomaa@cs.helsinki.fi</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:375432E5DF16E7B007EE5410D404654EEA80F719</idno><date when="2002" year="2002">2002</date><idno type="doi">10.1007/3-540-48050-1_27</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-ZB6H7V1Q-L/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000E33</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000E33</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Partition-Refining Algorithms for Learning Finite State Automata</title><author><name sortKey="Elomaa, Tapio" sort="Elomaa, Tapio" uniqKey="Elomaa T" first="Tapio" last="Elomaa">Tapio Elomaa</name><affiliation><mods:affiliation>Department of Computer Science, University of Helsinki, Teollisuuskatu 23, P. O. Box 26, FIN-00014, Finland</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: elomaa@cs.helsinki.fi</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="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: Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence. In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language. We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of k-reversible languages. Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.</div></front></TEI><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Tapio Elomaa</name><affiliations><json:string>Department of Computer Science, University of Helsinki, Teollisuuskatu 23, P. O. Box 26, FIN-00014, Finland</json:string><json:string>E-mail: elomaa@cs.helsinki.fi</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-ZB6H7V1Q-L</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence. In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language. We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of k-reversible languages. Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.</abstract><qualityIndicators><refBibsNative>false</refBibsNative><abstractWordCount>213</abstractWordCount><abstractCharCount>1462</abstractCharCount><keywordCount>0</keywordCount><score>9.242</score><pdfWordCount>4686</pdfWordCount><pdfCharCount>24396</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>12</pdfPageCount><pdfPageSize>430 x 650 pts</pdfPageSize></qualityIndicators><title>Partition-Refining Algorithms for Learning Finite State Automata</title><chapterId><json:string>27</json:string><json:string>Chap27</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>2002</copyrightDate><issn><json:string>0302-9743</json:string></issn><editor><json:item><name>G. Goos</name></json:item><json:item><name>J. Hartmanis</name></json:item><json:item><name>J. van Leeuwen</name></json:item></editor></serie><host><title>Foundations of Intelligent Systems</title><language><json:string>unknown</json:string></language><copyrightDate>2002</copyrightDate><doi><json:string>10.1007/3-540-48050-1</json:string></doi><issn><json:string>0302-9743</json:string></issn><eisbn><json:string>978-3-540-48050-1</json:string></eisbn><bookId><json:string>3-540-48050-1</json:string></bookId><isbn><json:string>978-3-540-43785-7</json:string></isbn><volume>2366</volume><pages><first>232</first><last>243</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Mohand-Saïd Hacid</name><affiliations><json:string>UFR d’Informatique, Université Claude Bernard Lyon I, 8, boulevard Niels Bohr, 69622, Villeurbanne Cedex, France</json:string><json:string>E-mail: mshacid@bat710.univ-lyon1.fr</json:string></affiliations></json:item><json:item><name>Zbigniew W. Raś</name><affiliations><json:string>Dept. of Computer Science College of IT, University of North Carolina, 28223, Charlotte, NC, USA</json:string><json:string>E-mail: ras@uncc.edu</json:string></affiliations></json:item><json:item><name>Djamel A. Zighed</name><affiliations><json:string>Băt. L. Equipe de Recherche en Ingénierie des Connaissances, Université Lumière Lyon 2, 5, avenue Pierre Mendes-France, 69676, Bron Cedex, France</json:string><json:string>E-mail: zighed@univ-lyon2.fr</json:string></affiliations></json:item><json:item><name>Yves Kodratoff</name><affiliations><json:string>LRI, Université Paris Sud, Băt. 490, 91405, Orsay Cedex, France</json:string><json:string>E-mail: yk@lri.fr</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Information Storage and Retrieval</value></json:item><json:item><value>Information Systems Applications (incl.Internet)</value></json:item><json:item><value>User Interfaces and Human Computer Interaction</value></json:item><json:item><value>Database Management</value></json:item><json:item><value>Computers and Society</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-ZB6H7V1Q-L</json:string></ark><publicationDate>2002</publicationDate><copyrightDate>2002</copyrightDate><doi><json:string>10.1007/3-540-48050-1_27</json:string></doi><id>375432E5DF16E7B007EE5410D404654EEA80F719</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-ZB6H7V1Q-L/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-ZB6H7V1Q-L/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-ZB6H7V1Q-L/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Partition-Refining Algorithms for Learning Finite State Automata</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="2002">2002</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">Partition-Refining Algorithms for Learning Finite State Automata</title><author><persName><forename type="first">Tapio</forename><surname>Elomaa</surname></persName><email>elomaa@cs.helsinki.fi</email><affiliation><orgName type="department">Department of Computer Science</orgName><orgName type="institution">University of Helsinki</orgName><address><postBox>P. O. Box 26</postBox><street>Teollisuuskatu 23</street><postCode>FIN-00014</postCode><country key="FI">FINLAND</country></address></affiliation></author><idno type="istex">375432E5DF16E7B007EE5410D404654EEA80F719</idno><idno type="ark">ark:/67375/HCB-ZB6H7V1Q-L</idno><idno type="DOI">10.1007/3-540-48050-1_27</idno></analytic><monogr><title level="m" type="main">Foundations of Intelligent Systems</title><title level="m" type="sub">13th International Symposium, ISMIS 2002 Lyon, France, June 27–29, 2002 Proceedings</title><title level="m" type="part">Learning and Knowledge Discovery</title><idno type="DOI">10.1007/3-540-48050-1</idno><idno type="book-id">3-540-48050-1</idno><idno type="ISBN">978-3-540-43785-7</idno><idno type="eISBN">978-3-540-48050-1</idno><idno type="chapter-id">Chap27</idno><idno type="part-id">Part7</idno><editor><persName><forename type="first">Mohand-Saïd</forename><surname>Hacid</surname></persName><email>mshacid@bat710.univ-lyon1.fr</email><affiliation><orgName type="department">UFR d’Informatique</orgName><orgName type="institution">Université Claude Bernard Lyon I</orgName><address><street>8, boulevard Niels Bohr</street><postCode>69622</postCode><settlement>Villeurbanne Cedex</settlement><country key="FR">FRANCE</country></address></affiliation></editor><editor><persName><forename type="first">Zbigniew</forename><forename type="first">W.</forename><surname>Raś</surname></persName><email>ras@uncc.edu</email><affiliation><orgName type="department">Dept. of Computer Science College of IT</orgName><orgName type="institution">University of North Carolina</orgName><address><settlement>Charlotte</settlement><region>NC</region><postCode>28223</postCode><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Djamel</forename><forename type="first">A.</forename><surname>Zighed</surname></persName><email>zighed@univ-lyon2.fr</email><affiliation><orgName type="department">Băt. L. Equipe de Recherche en Ingénierie des Connaissances</orgName><orgName type="institution">Université Lumière Lyon 2</orgName><address><street>5, avenue Pierre Mendes-France</street><postCode>69676</postCode><settlement>Bron Cedex</settlement><country key="FR">FRANCE</country></address></affiliation></editor><editor><persName><forename type="first">Yves</forename><surname>Kodratoff</surname></persName><email>yk@lri.fr</email><affiliation><orgName type="department">LRI</orgName><orgName type="institution">Université Paris Sud</orgName><address><street>Băt. 490</street><postCode>91405</postCode><settlement>Orsay Cedex</settlement><country key="FR">FRANCE</country></address></affiliation></editor><imprint><biblScope unit="vol">2366</biblScope><biblScope unit="page" from="232">232</biblScope><biblScope unit="page" to="243">243</biblScope><biblScope unit="chapter-count">64</biblScope><biblScope unit="part-chapter-count">4</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><editor><persName><forename type="first">G.</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">J.</forename><surname>Hartmanis</surname></persName></editor><editor><persName><forename type="first">J.</forename><nameLink>van</nameLink><surname>Leeuwen</surname></persName></editor><idno type="pISSN">0302-9743</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence.</p><p>In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language.</p><p>We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of <hi rend="italic">k</hi>-reversible languages.</p><p>Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.</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>I21017</label><item><term type="Secondary" subtype="priority-1">Artificial Intelligence (incl. Robotics)</term></item><label>I18032</label><item><term type="Secondary" subtype="priority-2">Information Storage and Retrieval</term></item><label>I18040</label><item><term type="Secondary" subtype="priority-3">Information Systems Applications (incl.Internet)</term></item><label>I18067</label><item><term type="Secondary" subtype="priority-4">User Interfaces and Human Computer Interaction</term></item><label>I18024</label><item><term type="Secondary" subtype="priority-5">Database Management</term></item><label>I24040</label><item><term type="Secondary" subtype="priority-6">Computers and Society</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-ZB6H7V1Q-L/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><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" TocLevels="0"><BookID>3-540-48050-1</BookID><BookTitle>Foundations of Intelligent Systems</BookTitle><BookSubTitle>13th International Symposium, ISMIS 2002 Lyon, France, June 27–29, 2002 Proceedings</BookSubTitle><BookVolumeNumber>2366</BookVolumeNumber><BookSequenceNumber>2366</BookSequenceNumber><BookDOI>10.1007/3-540-48050-1</BookDOI><BookTitleID>72398</BookTitleID><BookPrintISBN>978-3-540-43785-7</BookPrintISBN><BookElectronicISBN>978-3-540-48050-1</BookElectronicISBN><BookChapterCount>64</BookChapterCount><BookHistory><OnlineDate><Year>2002</Year><Month>6</Month><Day>21</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2002</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I21017" Priority="1" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I18032" Priority="2" Type="Secondary">Information Storage and Retrieval</BookSubject><BookSubject Code="I18040" Priority="3" Type="Secondary">Information Systems Applications (incl.Internet)</BookSubject><BookSubject Code="I18067" Priority="4" Type="Secondary">User Interfaces and Human Computer Interaction</BookSubject><BookSubject Code="I18024" Priority="5" Type="Secondary">Database Management</BookSubject><BookSubject Code="I24040" Priority="6" Type="Secondary">Computers and Society</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Mohand-Saïd</GivenName><FamilyName>Hacid</FamilyName></EditorName><Contact><Email>mshacid@bat710.univ-lyon1.fr</Email></Contact></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Zbigniew</GivenName><GivenName>W.</GivenName><FamilyName>Raś</FamilyName></EditorName><Contact><Email>ras@uncc.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Djamel</GivenName><GivenName>A.</GivenName><FamilyName>Zighed</FamilyName></EditorName><Contact><Email>zighed@univ-lyon2.fr</Email></Contact></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Yves</GivenName><FamilyName>Kodratoff</FamilyName></EditorName><Contact><Email>yk@lri.fr</Email></Contact></Editor><Affiliation ID="Aff1"><OrgDivision>UFR d’Informatique</OrgDivision><OrgName>Université Claude Bernard Lyon I</OrgName><OrgAddress><Street>8, boulevard Niels Bohr</Street><Postcode>69622</Postcode><City>Villeurbanne Cedex</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Dept. of Computer Science College of IT</OrgDivision><OrgName>University of North Carolina</OrgName><OrgAddress><City>Charlotte</City><State>NC</State><Postcode>28223</Postcode><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>Băt. L. Equipe de Recherche en Ingénierie des Connaissances</OrgDivision><OrgName>Université Lumière Lyon 2</OrgName><OrgAddress><Street>5, avenue Pierre Mendes-France</Street><Postcode>69676</Postcode><City>Bron Cedex</City><Country>France</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgDivision>LRI</OrgDivision><OrgName>Université Paris Sud</OrgName><OrgAddress><Street>Băt. 490</Street><Postcode>91405</Postcode><City>Orsay Cedex</City><Country>France</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part7"><PartInfo TocLevels="0"><PartID>7</PartID><PartSequenceNumber>7</PartSequenceNumber><PartTitle>Learning and Knowledge Discovery</PartTitle><PartChapterCount>4</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookID>3-540-48050-1</BookID><BookTitle>Foundations of Intelligent Systems</BookTitle></PartContext></PartInfo><Chapter ID="Chap27" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>27</ChapterID><ChapterDOI>10.1007/3-540-48050-1_27</ChapterDOI><ChapterSequenceNumber>27</ChapterSequenceNumber><ChapterTitle Language="En">Partition-Refining Algorithms for Learning Finite State Automata</ChapterTitle><ChapterFirstPage>232</ChapterFirstPage><ChapterLastPage>243</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2002</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2002</Year><Month>6</Month><Day>20</Day></RegistrationDate><OnlineDate><Year>2002</Year><Month>6</Month><Day>21</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><PartID>7</PartID><BookID>3-540-48050-1</BookID><BookTitle>Foundations of Intelligent Systems</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff5"><AuthorName DisplayOrder="Western"><GivenName>Tapio</GivenName><FamilyName>Elomaa</FamilyName></AuthorName><Contact><Email>elomaa@cs.helsinki.fi</Email></Contact></Author><Affiliation ID="Aff5"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Helsinki</OrgName><OrgAddress><Postbox>P. O. Box 26</Postbox><Street>Teollisuuskatu 23</Street><Postcode>FIN-00014</Postcode><Country>Finland</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence.</Para><Para>In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language.</Para><Para>We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of <Emphasis Type="Italic">k</Emphasis>-reversible languages.</Para><Para>Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book><SubSeries><SubSeriesInfo><SubSeriesID>1244</SubSeriesID><SubSeriesTitle Language="En">Lecture Notes in Artificial Intelligence</SubSeriesTitle><SubSeriesSubTitle Language="En">Subseries of Lecture Notes in Computer Science</SubSeriesSubTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><GivenName>G.</GivenName><FamilyName>Carbonell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>J.</GivenName><FamilyName>Siekmann</FamilyName></EditorName></Editor></EditorGroup></SubSeriesHeader></SubSeries></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Partition-Refining Algorithms for Learning Finite State Automata</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Partition-Refining Algorithms for Learning Finite State Automata</title></titleInfo><name type="personal"><namePart type="given">Tapio</namePart><namePart type="family">Elomaa</namePart><affiliation>Department of Computer Science, University of Helsinki, Teollisuuskatu 23, P. O. Box 26, FIN-00014, Finland</affiliation><affiliation>E-mail: elomaa@cs.helsinki.fi</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">2002</dateIssued><copyrightDate encoding="w3cdtf">2002</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: Regular language learning from positive examples alone is infeasible. Subclasses of regular languages, though, can be inferred from positive examples only. The most common approach for learning such is the specific-to-general technique of merging together either states of an initial finite state automaton or nonterminals in a regular grammar until convergence. In this paper we seek to unify some language learning approaches under the general-to-specific learning scheme. In automata terms it is implemented by refining the partition of the states of the automaton starting from one block until desired decomposition is obtained; i.e., until all blocks in the partition are uniform according to the predicate determining the properties required from the language. We develop a series of learning algorithms for well-known classes of regular languages as instantiations of the same master algorithm. Through block decomposition we are able to describe in the same scheme, e.g., the learning by rote approach of minimizing the number of states in the automaton and inference of k-reversible languages. Under the worst-case analysis partition-refinement is less efficient than alternative approaches. However, for many cases it turns out more efficient in practice. Moreover, it ensures the inference of the canonical automaton, whereas the state-merging approach will leave excessive states to the final automaton without a separate minimization step.</abstract><relatedItem type="host"><titleInfo><title>Foundations of Intelligent Systems</title><subTitle>13th International Symposium, ISMIS 2002 Lyon, France, June 27–29, 2002 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Mohand-Saïd</namePart><namePart type="family">Hacid</namePart><affiliation>UFR d’Informatique, Université Claude Bernard Lyon I, 8, boulevard Niels Bohr, 69622, Villeurbanne Cedex, France</affiliation><affiliation>E-mail: mshacid@bat710.univ-lyon1.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Zbigniew</namePart><namePart type="given">W.</namePart><namePart type="family">Raś</namePart><affiliation>Dept. of Computer Science College of IT, University of North Carolina, 28223, Charlotte, NC, USA</affiliation><affiliation>E-mail: ras@uncc.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Djamel</namePart><namePart type="given">A.</namePart><namePart type="family">Zighed</namePart><affiliation>Băt. L. Equipe de Recherche en Ingénierie des Connaissances, Université Lumière Lyon 2, 5, avenue Pierre Mendes-France, 69676, Bron Cedex, France</affiliation><affiliation>E-mail: zighed@univ-lyon2.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Yves</namePart><namePart type="family">Kodratoff</namePart><affiliation>LRI, Université Paris Sud, Băt. 490, 91405, Orsay Cedex, France</affiliation><affiliation>E-mail: yk@lri.fr</affiliation><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">2002</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="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I18032">Information Storage and Retrieval</topic><topic authority="SpringerSubjectCodes" authorityURI="I18040">Information Systems Applications (incl.Internet)</topic><topic authority="SpringerSubjectCodes" authorityURI="I18067">User Interfaces and Human Computer Interaction</topic><topic authority="SpringerSubjectCodes" authorityURI="I18024">Database Management</topic><topic authority="SpringerSubjectCodes" authorityURI="I24040">Computers and Society</topic></subject><identifier type="DOI">10.1007/3-540-48050-1</identifier><identifier type="ISBN">978-3-540-43785-7</identifier><identifier type="eISBN">978-3-540-48050-1</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">72398</identifier><identifier type="BookID">3-540-48050-1</identifier><identifier type="BookChapterCount">64</identifier><identifier type="BookVolumeNumber">2366</identifier><identifier type="BookSequenceNumber">2366</identifier><identifier type="PartChapterCount">4</identifier><part><date>2002</date><detail type="part"><title>Learning and Knowledge Discovery</title></detail><detail type="volume"><number>2366</number><caption>vol.</caption></detail><extent unit="pages"><start>232</start><end>243</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2002</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">2002</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Artificial Intelligence</title><subTitle>Subseries of Lecture Notes in Computer Science</subTitle></titleInfo><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">van Leeuwen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Mohand-Saïd</namePart><namePart type="family">Hacid</namePart><affiliation>UFR d’Informatique, Université Claude Bernard Lyon I, 8, boulevard Niels Bohr, 69622, Villeurbanne Cedex, France</affiliation><affiliation>E-mail: mshacid@bat710.univ-lyon1.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Zbigniew</namePart><namePart type="given">W.</namePart><namePart type="family">Raś</namePart><affiliation>Dept. of Computer Science College of IT, University of North Carolina, 28223, Charlotte, NC, USA</affiliation><affiliation>E-mail: ras@uncc.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Djamel</namePart><namePart type="given">A.</namePart><namePart type="family">Zighed</namePart><affiliation>Băt. L. Equipe de Recherche en Ingénierie des Connaissances, Université Lumière Lyon 2, 5, avenue Pierre Mendes-France, 69676, Bron Cedex, France</affiliation><affiliation>E-mail: zighed@univ-lyon2.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Yves</namePart><namePart type="family">Kodratoff</namePart><affiliation>LRI, Université Paris Sud, Băt. 490, 91405, Orsay Cedex, France</affiliation><affiliation>E-mail: yk@lri.fr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="given">G.</namePart><namePart type="family">Carbonell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">J.</namePart><namePart type="family">Siekmann</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="SubSeriesID">1244</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2002</recordOrigin></recordInfo></relatedItem><identifier type="istex">375432E5DF16E7B007EE5410D404654EEA80F719</identifier><identifier type="ark">ark:/67375/HCB-ZB6H7V1Q-L</identifier><identifier type="DOI">10.1007/3-540-48050-1_27</identifier><identifier type="ChapterID">27</identifier><identifier type="ChapterID">Chap27</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2002</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, 2002</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-ZB6H7V1Q-L/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Informatique/explor/SgmlV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000E33 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000E33 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Informatique
|area= SgmlV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:375432E5DF16E7B007EE5410D404654EEA80F719
|texte= Partition-Refining Algorithms for Learning Finite State Automata
}}
| This area was generated with Dilib version V0.6.33. |  |