Grammatical Inference - a short survey
The topic of Grammatical Inference is the automatic
induction of grammars, automata etc. according to
some learning protocol.
We have published papers on two of the most proliferate
models, namely Gold's model of learning from text,
also called identification in the limit (from positive presentation),
and Angluin's
model of query learning. In our relevant publications
listed below, we marked the employed learning models.
Papers
Some of the papers are electronically available, see
our complete list of publications.
Otherwise, feel free to contact me.
Learning from Text
- H. Fernau.
Technical Report WSI-99-23, Universität Tübingen, Wilhelm-Schickard-Institut für Informatik, Sand 13, D-72076 Tübingen, Germany, Dec. 1999.
The material has been presented at the
Sixth International Symposium on Artificial Intelligence and Mathematics (AMAI),
Fort Lauderdale, Florida, Jan. 5th till Jan. 7th, 2000.
A thoroughly revised version has been submitted for publication
to the corresponding journal.
- H. Fernau and M. Holzer.
External Contextual and Conditional Languages.
IN: C. Martin-Vide and Gh. Paun (eds.), Recent Topics in Mathematical and Computational Linguistics, pages 104-120. Bucharest: The Publishing House of the Romanian Academy, 2000.
- H. Fernau.
PC grammar systems with terminal transmission,
IN: R. Freund and A. Kelemenova (eds.), Proceedings of the
International Workshop
Grammar Systems 2000, pages 229-252.
Extended version is available as
Technical Report WSI-2000-15. A slightly modified
journal version has been published in Acta Informatica, 37 (2001), pages 511-540.
- H. Fernau. k-gram extensions of terminal distinguishable languages,
IN: Proceedings of the
International Conference on Pattern Recognition ICPR 2000,
vol. 2, pages 125-128. © IEEE Press, 2000.
The results will be also published in the journal version of the
following paper.
- H. Fernau.
Identification of function distinguishable languages,
IN: H. Arimura, S. Jain and A. Sharma (ed.), Proceedings of the 11th International Conference on
Algorithmic Learning Theory (ALT 2000),
© Springer-Verlag,
LNCS 1968, pages 116-130.
A preliminary version appeared as Technical Report.
A journal version, containing also the result of the previous and the subsequent publication, will be published in Theoretical Computer Science.
- H. Fernau.
Approximative Learning of Regular Languages. Technical Report.
An extended abstract appeared IN: L. Pacholski and P. Ruzicka (ed.):
SOFSEM'01; Theory and Practice of Informatics,
© Springer-Verlag,
LNCS 2234, pages 223-232.
- H. Fernau.
Learning XML grammars. IN: P. Perner (ed.), Proceedings International Workshop on Machine Learning and Data Mining in Pattern Recognition (MLDM 2001).
© Springer-Verlag,
LNCS 2123, pages 73-87. There is also an (earlier) Technical Report version.
- H. Fernau. Learning tree languages from text. Manuscript submitted, 2001.
There is also an (earlier) Technical Report version.
Query Learning
- H. Fernau.
Efficient learning of some linear matrix languages, © Springer-Verlag,
Proceedings of COCOON'99 (
LNCS 1627), pages 221-230, 1999.
A long version is available as Technical Report WSI-2000-9.
An updated version of this report is accepted for publication
in Theoretical Computer Science under the title
Even linear simple matrix languages: formal language properties and grammatical inference and can be retrieved from Elsevier.
The long versions also contain the results of the following companion
conference paper:
- H. Fernau.
Even linear simple matrix languages: formal language aspects.
IN: C.S. Calude, M.J. Dinneen and S. Sburlan (ed.),
Discrete Mathematics and Theoretical Computer Science (DMTCS 2001),
© Springer-Verlag , pages 81-96.
Mixed Techniques
Software
Agnes Radl has implemented the learning algorithms concerning function distinguishable languages, as well as concerning the inference of DTDs for
XML documents.
The software is available here.
Henning Fernau
Last modified: Mon Jan 21 08:41:19 MET 2002