Learning Rational Functions

Abstract : Rational functions are transformations from words to words that can be defined by string transducers. Rational functions are also captured by deterministic string transducers with lookahead. We show for the first time that the class of rational functions can be learned in the limit with polynomial time and data, when represented by string transducers with lookahead in the diagonal-minimal normal form that we introduce.
Document type :
Conference papers
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00692341
Contributor : Joachim Niehren <>
Submitted on : Tuesday, May 29, 2012 - 12:00:19 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on: Thursday, December 15, 2016 - 2:50:20 AM

File

0.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00692341, version 1

Collections

Citation

Adrien Boiret, Aurélien Lemay, Joachim Niehren. Learning Rational Functions. 16th International Conference on Developments of Language Theory, Apr 2012, Taipee, Taiwan. ⟨hal-00692341⟩

Share

Metrics

Record views

361

Files downloads

462