Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata

Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata. Higuera, de la, C., & Thollard, F. In Grammatical Inference: Algorithms and Applications, of Lecture Notes in Computer Science, pages 141--156. Springer Berlin Heidelberg, 2000. 00028

Paper abstract bibtex

The current formal proof that stochastic deterministic finite automata can be identified in the limit with probability one makes use of a simplified state-merging algorithm. We prove in this paper that the Alergia algorithm, and its extensions, which may use some blue fringe type of ordering, can also identify distributions generated by stochastic deterministic finite automata. We also give a new algorithm enabling us to identify the actual probabilities, even though in practice, the number of examples needed can still be overwhelming.

@incollection{ higuera_identification_2000,
  series = {Lecture {Notes} in {Computer} {Science}},
  title = {Identification in the {Limit} with {Probability} {One} of {Stochastic} {Deterministic} {Finite} {Automata}},
  copyright = {©2000 Springer-Verlag Berlin Heidelberg},
  isbn = {978-3-540-41011-9, 978-3-540-45257-7},
  url = {http://link.springer.com.gaelnomade.ujf-grenoble.fr/chapter/10.1007/978-3-540-45257-7_12},
  abstract = {The current formal proof that stochastic deterministic finite automata can be identified in the limit with probability one makes use of a simplified state-merging algorithm. We prove in this paper that the Alergia algorithm, and its extensions, which may use some blue fringe type of ordering, can also identify distributions generated by stochastic deterministic finite automata. We also give a new algorithm enabling us to identify the actual probabilities, even though in practice, the number of examples needed can still be overwhelming.},
  language = {en},
  number = {1891},
  urldate = {2015-04-21TZ},
  booktitle = {Grammatical {Inference}: {Algorithms} and {Applications}},
  publisher = {Springer Berlin Heidelberg},
  author = {Higuera, Colin de la and Thollard, Franck},
  editor = {Oliveira, Arlindo L.},
  year = {2000},
  note = {00028},
  keywords = {Algorithm Analysis and Problem Complexity, Artificial Intelligence (incl. Robotics), Mathematical Logic and Formal Languages, Pattern Recognition, grammatical inference, identification with probability one, polynomial learning, stochastic deterministic finite automaton},
  pages = {141--156}
}

Downloads: 0

{"_id":"5yQgPMJ7mpwS8yFch","authorIDs":[],"author_short":["Higuera","de<nbsp>la, C.","Thollard, F."],"bibbaseid":"higuera-denbspla-thollard-identificationinthelimitwithprobabilityoneofstochasticdeterministicfiniteautomata-2000","bibdata":{"abstract":"The current formal proof that stochastic deterministic finite automata can be identified in the limit with probability one makes use of a simplified state-merging algorithm. We prove in this paper that the Alergia algorithm, and its extensions, which may use some blue fringe type of ordering, can also identify distributions generated by stochastic deterministic finite automata. We also give a new algorithm enabling us to identify the actual probabilities, even though in practice, the number of examples needed can still be overwhelming.","author":["Higuera","de la, Colin","Thollard, Franck"],"author_short":["Higuera","de<nbsp>la, C.","Thollard, F."],"bibtex":"@incollection{ higuera_identification_2000,\n series = {Lecture {Notes} in {Computer} {Science}},\n title = {Identification in the {Limit} with {Probability} {One} of {Stochastic} {Deterministic} {Finite} {Automata}},\n copyright = {©2000 Springer-Verlag Berlin Heidelberg},\n isbn = {978-3-540-41011-9, 978-3-540-45257-7},\n url = {http://link.springer.com.gaelnomade.ujf-grenoble.fr/chapter/10.1007/978-3-540-45257-7_12},\n abstract = {The current formal proof that stochastic deterministic finite automata can be identified in the limit with probability one makes use of a simplified state-merging algorithm. We prove in this paper that the Alergia algorithm, and its extensions, which may use some blue fringe type of ordering, can also identify distributions generated by stochastic deterministic finite automata. We also give a new algorithm enabling us to identify the actual probabilities, even though in practice, the number of examples needed can still be overwhelming.},\n language = {en},\n number = {1891},\n urldate = {2015-04-21TZ},\n booktitle = {Grammatical {Inference}: {Algorithms} and {Applications}},\n publisher = {Springer Berlin Heidelberg},\n author = {Higuera, Colin de la and Thollard, Franck},\n editor = {Oliveira, Arlindo L.},\n year = {2000},\n note = {00028},\n keywords = {Algorithm Analysis and Problem Complexity, Artificial Intelligence (incl. Robotics), Mathematical Logic and Formal Languages, Pattern Recognition, grammatical inference, identification with probability one, polynomial learning, stochastic deterministic finite automaton},\n pages = {141--156}\n}","bibtype":"incollection","booktitle":"Grammatical Inference: Algorithms and Applications","copyright":"©2000 Springer-Verlag Berlin Heidelberg","editor":["Oliveira, Arlindo L."],"editor_short":["Oliveira, A.<nbsp>L."],"id":"higuera_identification_2000","isbn":"978-3-540-41011-9, 978-3-540-45257-7","key":"higuera_identification_2000","keywords":"Algorithm Analysis and Problem Complexity, Artificial Intelligence (incl. Robotics), Mathematical Logic and Formal Languages, Pattern Recognition, grammatical inference, identification with probability one, polynomial learning, stochastic deterministic finite automaton","language":"en","note":"00028","number":"1891","pages":"141--156","publisher":"Springer Berlin Heidelberg","series":"Lecture Notes in Computer Science","title":"Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata","type":"incollection","url":"http://link.springer.com.gaelnomade.ujf-grenoble.fr/chapter/10.1007/978-3-540-45257-7_12","urldate":"2015-04-21TZ","year":"2000","bibbaseid":"higuera-denbspla-thollard-identificationinthelimitwithprobabilityoneofstochasticdeterministicfiniteautomata-2000","role":"author","urls":{"Paper":"http://link.springer.com.gaelnomade.ujf-grenoble.fr/chapter/10.1007/978-3-540-45257-7_12"},"keyword":["Algorithm Analysis and Problem Complexity","Artificial Intelligence (incl. Robotics)","Mathematical Logic and Formal Languages","Pattern Recognition","grammatical inference","identification with probability one","polynomial learning","stochastic deterministic finite automaton"],"downloads":0},"bibtype":"incollection","biburl":"http://bibbase.org/zotero/ealprr","creationDate":"2015-04-22T00:12:57.201Z","downloads":0,"keywords":["algorithm analysis and problem complexity","artificial intelligence (incl. robotics)","mathematical logic and formal languages","pattern recognition","grammatical inference","identification with probability one","polynomial learning","stochastic deterministic finite automaton"],"search_terms":["identification","limit","probability","one","stochastic","deterministic","finite","automata","higuera","de<nbsp>la","thollard"],"title":"Identification in the Limit with Probability One of Stochastic Deterministic Finite Automata","year":2000,"dataSources":["fcy64Zdm28gydMmuE"]}