Inference of Reversible Languages
- 1 July 1982
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 29 (3) , 741-765
- https://doi.org/10.1145/322326.322334
Abstract
A famdy of efficient algorithms for referring certain subclasses of the regular languages from fmtte posttwe samples is presented These subclasses are the k-reversible languages, for k = 0, 1, 2, .... For each k there is an algorithm for finding the smallest k-reversible language containing any fimte posluve sample. It ts shown how to use this algorithm to do correct identification m the ILmlt of the k- reversible languages from posmve data A reversible language is one that Is k-reverstble for some k __ 0. An efficient algonthrn is presented for mfernng reversible languages from posmve and negative examples, and it is shown that it leads to correct identification m the hmlt of the class of reversible languages. Numerous examples are gtven to dlustrate the algorithms and their behaworKeywords
This publication has 17 references indexed in Scilit:
- Inductive inference of formal languages from positive dataInformation and Control, 1980
- On the complexity of minimum inference of regular setsInformation and Control, 1978
- Noncounting Context-Free LanguagesJournal of the ACM, 1978
- Complexity of automaton identification from given dataInformation and Control, 1978
- Toward a mathematical theory of inductive inferenceInformation and Control, 1975
- On the Synthesis of Finite-State Machines from Samples of Their BehaviorIEEE Transactions on Computers, 1972
- Some decidability results on grammatical inference and complexityInformation and Control, 1972
- General properties of star height of regular eventsJournal of Computer and System Sciences, 1970
- Language identification in the limitInformation and Control, 1967
- About Some Properties of Definite, Reverse-Definite and Related AutomataIEEE Transactions on Electronic Computers, 1966