Inductive Inference: Theory and Methods

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Inductive Inference: Theory and Methods

Full text

Pdf (2.51 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 15 , Issue 3 (September 1983) table of contents

Pages: 237 - 269

Year of Publication: 1983

ISSN:0360-0300

Authors

Dana Angluin	Department of Computer Science, Yale University, New Haven, Connecticut
Carl H. Smith	Department of Computer Science, The University of Maryland, College Park, Maryland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 249, Citation Count: 102

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/356914.356918 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ADELMAN, L., AND BLUM, M. 1975. Inductive inference and unsolvabiIity. Tech. Rep., Electrical Engineering and Computer Science Dept., Univ. of Calif., Berkeley.
	2	AN6LUIN, D. 1978. On the complexity of minimum inference of regular sets. Inf. Control 39, 337-350.
	3	ANCLUlN, D. 1980a. Inductive inference of formal languages from positive data. In{. Control 45, 117- 135.
	4	ANGLUIN, D. 1980b. Finding patterns common to a set of strings. J. Cornput. Syst. Sci. 21, 46-62.
	5	ANGLUIN, D. 1982a. A note on the number of queries needed to identify regular languages. In{. Control 51, 76-87.
	6	Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
	7	BARZDIN, J. M. 1972. Prognostication of automata and functions. In Information Processing 71, B. Gilchrist, Ed. Elsevier North-Holland, New York, pp. 81-84.
	8	BARZOtN, J. M. 1974a. On synthesizing programs given by examples. In Lecture Notes in Cornpurer Science, vol. 5. Springer-Verlag, New York, pp. 53-63.
	9	BARZm~, J. M. 1974b. Two theorems on the limiting synthesis of functions. Latv. Gos. Univ. Uch. Zapiski 210, 82-88 (in Russian).
	10	B~zI~I~, J. M., ANO FREIVALD, R. V. 1972. On the prediction of general recursive functions. Soy. Math. Dokl I3, 1224-1228.
	11	BARZOIN, J. M., ANO POONIEKS, K. M. 1973. The theory of inductive inference (in Russian). In Proceedings of the }st Conference on the Mathematical Foundations of Computer Science (High Tetras, Czechoslovakia). Math. inst. of the Sloyak Academy of Sciences, pp. 9-15.
	12	BERGER, J., AND PAIR, C. 1978. Inference for regular bilanguages. J. Comput. Sys. Sci. 16, 100-122.
	13	BIERMANN, A. W. 1972. On the inference of Turing machines from sample computations. Arti{. Intell. 3, 181-198.
	14	BIERMANN, A. W. 1975. The inference of regular LISP programs from examples. IEEE Trans. Syst. Man Cybern. SMC-8, 585-600.
	15	BIERMANI~, A. W., AND FELDMAN, J. A. 1972a. A survey of results in grammatical inference. In Frontiers of Pattern Recognition. Academic Press, New York.
	16	BIERMANN, A. W., AND FELDMAN, J. A. 1972b. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Comput. C- 21, 592-597.
	17	BIERMANN, A. W., AND KRISHNASWAMY, R. 1976. Constructing programs from example computations. IEEE Trans. Sofiw. Eng. SE-2, 141-153.
	18	BIERMANN, A. W., AND SMIW~, D. R. 1977. The hierarchical synthesis of LISP scanning functions. In Information Processing 77, B. Gilchrist, Ed. Elsevier North-Holland, New York, pp. 41- 45.
	19	BIERMANN, A. W., BAUM, R. I., ^No PETRY, F. E. 1975. Speeding up the synthesis of programs from traces. IEEE Trans. Comput. C-24, 122-136.
	20	BLUM, L., AND BLUM, M. 1975. Toward a mathematical theory of inductive inference. Inf. Control 28, 125-155.
	21	BLUM, M. 1967a. On the size of machines. In{. Control 11, 257-265.
	22	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	23	BRANDT, U. 1981. A characterization of identifiable sets. Preprint, Technische Hochschule Darmstadt, F.R.G.
	24	BRAYER, J. M., AND FU, K. S. 1977. A note on the k-tall method of tree grammar inference. IEEE Trans. Syst. Man Cybern. SMC-7, 293-300.
	25	BUCHANAN, B. G., AND FEIGENBAUM, E. A. 1978. Dendral and Meta-Dendral: Their applications dimension. Artif lnteU. 11, 5-24.
	26	BUNDY, A., AND SILVER, B. 1981. A critical survey of rule learning programs. Tech. Rep. 169, Dept. of Artificial Intelligence, Edinburgh Univ.
	27	John Case , Christopher Lynes, Machine Inductive Inference and Language Identification, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.107-115, July 12-16, 1982
	28	C^sE, J., AND NGo-MANc, UELLE, S. 1979. Refinements of inductive inference by Popperian machines. Tech. Rep., Dept. of Computer Science, State Univ. of New York, Buffalo.
	29	John Case , Carl Smith, Anomaly hierarchies of mechanized inductive inference, Proceedings of the tenth annual ACM symposium on Theory of computing, p.314-319, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804360]
	30	CASE, J., A~D SMrrH, C. 1983. Comparison of identification criteria for machine inductive inference. Theor. Comput. Sci. 25, 193-220.
	31	Gregory J. Chaitin, Information-Theoretic Limitations of Formal Systems, Journal of the ACM (JACM), v.21 n.3, p.403-424, July 1974 [doi>10.1145/321832.321839]
	32	Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM (JACM), v.22 n.3, p.329-340, July 1975 [doi>10.1145/321892.321894]
	33	CHAITIN, G. J. 1976. Information-theoretic characterizations of recursive infinite strings. Theor. Comput. ScL 2, 45-48.
	34	CnEN, K. J. 1982. Tradeoffs in the inductive inference of nearly minimal size programs. Int. Control 52, 68-86.
	35	COOK, C. M., ROSENFELD, A., AND ARONSON, A. R. 1976. Grammatical inference by hill-climbing. In{. Sci. 10, 59-80.
	36	COULON, D., AND KAYSER, D. 1979. Construction of natural language sentence acceptors by a supervised learning technique. IEEE Trans. Pattern Anal. Mach. lntelL PAMI-1, 94-99.
	37	CgESPI-Rr~(~HIZZl, S. 1972. An effective model for grammar inference. In Information Processing 71, B. Gilchrist, Ed. Elsevier North-Holland, New York, pp. 524-529.
	38	CR!~SPI-REC. HIZZl, S., AND MANDRIOLI, D. 1980a. Abstract profiles for context-free languages. Tech. Rep. 80-6, Ist. eli Elettrotechnica ed Elettronica del Politechnico di Milano, Milan, Italy.
	39	CRESrI-Rr. Gt!IZZl, S., AND MANORIOLI, D. 1980b. Inferring grammars by means of pro~des: a unifying view. Internal report, Ist. di Elettrotechnica ed Elettronica de{ Politechnico di Milano, Milan, Italy.
	40	S. Crespi-Reghizzi , M. A. Melkanoff , L. Lichten, The use of grammatical inference for designing programming languages, Communications of the ACM, v.16 n.2, p.83-90, Feb. 1973 [doi>10.1145/361952.361958]
	41	S. Crespi-Reghizzi , G. Guida , D. Mandrioli, Noncounting Context-Free Languages, Journal of the ACM (JACM), v.25 n.4, p.571-580, Oct. 1978 [doi>10.1145/322092.322098]
	42	Robert P. Daley, An Example of Information and Computation Resource Trade-Off, Journal of the ACM (JACM), v.20 n.4, p.687-695, Oct. 1973 [doi>10.1145/321784.321794]
	43	DALP. Y, R. 1977. On the inference of optimal descriptions. Theor. Comput. Sci. 4, 301-319.
	44	DALE~, R. 1983. On the error correcting power of pluralism in inductive inference. Theor. Comput. Sci. 24, 95-104.
	45	DALE~, R., AND SMITH, C. 1983. On the complexity of inductive inference. Tech. Pep. 83-4, Dept. of Computer Science, Univ. of Pittsburgh.
	46	DIETI'ERIClt, T. G., AND MICHALSKI, R. S. 1979. Learning and generalization of characteristic descriptions: Evaluation criteria and comparative review of selected methods. In Proceedings of the 6th International Joint Con/erence on Artificial Intelligence (Tokyo, Aug.). International Joint Council on Artificial Intelligence, pp. 223-231.
	47	DIETI'ERICH, T. G., LONDON, R., CLARKSON, K., AND DROME~, R. 1982. Learning and inductive inference. In The Handbook of Arti{icial Intelligence, P. Cohen and E. Feigenbaum Eds. Kaufman, Los Altos, Calif., pp. 323-512.
	48	P. G. Doucet, The Syntactic Inference Problem for D0L-Sequences, L Systems, Most of the papers were presented at a conference in Aarhus, Denmark, p.146-161, January 14-25, 1974
	49	FELDMAN, J. A. 1967. First thoughts on grammatical inference. Tech. Rep., Computer Science Dept., Artificial Intelligence Memo 55, Stanford UniversiW, Stanford, Calif.
	50	FELt)MAN, J. A. 1972. Some decidability results in grammatical inference. In{. Control 20, 244-262.
	51	FELOMAN, J. A., AND SmELOS, P. 1977. Total complexity and the inference of best programs. Math. $yst. Theory. 10, 181-191.
	52	Jerome A. Feldman , James Gips , James J. Horning , Stephen Reder, Grammatical complexity and inference, Stanford University, Stanford, CA, 1969
	53	FELICIANGELI, H., AND HERMAN, G. 1977. Algorithms for producing grammars from sample derivations: A common problem of formal language theory and developmental biology. J. Cornput. Syst. Sci. 7, 97-118.
	54	FLANAGAN, P. A. 1981. A discrete model of semantic learning. Tech. Rep. CS-79, Computer Science Dept., Brown University, Providence, R. I.
	55	FREDKiN, E. 1964. Techniques using LISP for automatically discovering interesting relations in data. In The Programming Language LISP, Berkey, Ed. M.I.T. Press, Cambridge, Mass., pp. 108- 124.
	56	FREIVALD, R. V. 1974. On the limit synthesis of numbers of general recursive functions in various computable numerations. Soy. Math. Dokl. 15, 1681-1683.
	57	Fttt~IVALO, R. V. 1975a. Minimal Godel numbers and their identification in the limit. In Lecture Notes in Computer Science, voL 32. Springer-Verlag, New York, pp. 219-225.
	58	FP. EIVALD, R. V. 1975b. On the complexity and optimality of computation in the limit. Latv. Gos. Univ. Uch. Zapiski 233, 155-173 (in Russian).
	59	FREWALD, R. V. 1979. Finite identification of general recursive functions by probabilistic strategies. In Proceedings o{ the Conference on Algebraic, Arithmetic, and Categorial Methods in Cornputation Theory (Berlin, Sept. 1979). L. Budach, Ed. Akademie-Verlag, Berlin, DDR, pp. 138-145.
	60	FREIVALO, R. V., AND WIEHAOEN, R. 1979. Inductive inference with additional information. E/ectron. Informationsverarb. Kybern. (EIK) 18, 179- 185.
	61	F!tEIVALD, R. V., KINBEP,, E. B., ANt) WIi~ttAGP-N, R. 1982. Inductive inference and computable oneone numberings. Z. Logik Grundlag. Math. 23, 463-479.
	62	FRIEDBERG, R, 1958. Three theorems on recursive enumeration. J. Symb. Logic 23, 309-316.
	63	Fu, K. S. 1975. Syntactic Methods in Pattern Recognition. Academic Press, New York.
	64	Fu K. S. 1977. Syntactic Pattern Recognition, Applications. Springer-Verlag, New York.
	65	Fu, K. S. 1982. Syntactic Pattern Recognition and Applications. Prentice-Hall, New York.
	66	Fu, K. S., At~O BOOTH, T. L. 1975. Grammatical inference: introduction and survey, parts 1 and 2. IEEE Trans. Syst. Man Cybern. SMC-5, 95-111, 409-423.
	67	GACS, P. 1983. On the relationship between descriptional complexity and algorithmic probability. Theor. Comput. ScL, 22, 1, 2, 71-93.
	68	GAINES, B. R. 1976. Behavior/structure transformations under uncertainty. Int. J. Man-Math. Stud. 8, 337-365.
	69	GAINES, B. R. 1978. Maryanski's grammatical inferencer. IEEE Trans. Comput. C-28, 62-64.
	70	GOLD, E. M. 1967. Language identification in the limit. Inf. Control lO, 447-474.
	71	GOLD, E. M. 1972. System identification via state characterization. AuWmatica 8, 621-636.
	72	GOLD, E. M. 1978. Complexity of automaton identification from given data. Inf. Control. 37, 302- 320.
	73	GONZALEZ, R. C., A~D TnOMASON, M. G. 1978. Syntactic Pattern Recognition, An Introduction. Addison-Wesley, Reading, Mass.
	74	GONZALEZ, R. C., EDWARDS, J. J., AND THOMASON, M. G. 1976. An algorithm for the inference of tree grammars. Int. J. Comput. Inf. ScL 5, 145- 164.
	75	HANDY, S. 1975. Synthesis of LISP programs from examples. In Proceedings of the 4th International Joint Conference on Artificial Intelligence (Tibilsi, Georgia, USSR, Sept.). International Joint Council on Artificial Intelligence, pp. 268-273.
	76	Frederick Hayes-Roth , John McDermott, An interference matching technique for inducing abstractions, Communications of the ACM, v.21 n.5, p.401-411, May 1978 [doi>10.1145/359488.359503]
	77	HOP, NING, J. J. 1969. A study of grammatical inference. Ph.D. dissertation, Computer Science Dept., Stanford Univ., Stanford, Calif.
	78	JANTKE, K. P. 1979. Natural properties of strategies identifying recursive functions. Elektron. In{ormationsverarb. Kybern. (EIK) 15, 487-496.
	79	JANTKE, K. P., AND BEICK, H. R. 1981. Combining postulates of naturalness in inductive inference. Elektron. Informationsverarb. Kybern. (ELK) 17, 465-484.
	80	JOUANNAUD, J. P., AND GUIHO, G. t979. Inference of functions with an interactive system. In Machine Intelligence 9, J. E. Hayes, D. Michie, and L. I. Mikulich, Eds. Wiley, New York, pp. 227- 250.
	81	JOUANNAUD, J. P., AND KoDsavorr, Y. 1979. Characterization of a class of functions synthesized by a Summers-like method using a B.M.W. matching technique. In Proceedings of the 6th International Joint Conference on Artificial lnteltigence (Tokyo, Aug.). international Joint Council on Artificial Intelligence, pp. 440-447.
	82	JOUANNAUD, J. P., ANO KOORATOFF, Y. 1980. An automatic construction of LISP programs by transformations of functions synthesized from their input-output behavior. Int. J. Policy Analy. Inf. Syst. 4, 331-358.
	83	JOUANNAUD, J. P., GUiHO, G., ANO TREUIL, T. P. 1977. S{SP/1, an interactive system able to synthesize functions from examples. In Proceedings of the 5th International Joint Conference on Artificial Intelligence (Cambridge, Mass., Aug.). International Joint Council on Artificial Intelligence, pp. 412-418.
	84	JUNG, H. 1977. Zur Untersuchung yon abstrakten interaktiven Erkennungssystemen. Ph.D. dissertation, Humbolt University, Berlin, GDR.
	85	KLETTE, R., AND WIEHAGEN, R. 1980. Research in the theory of inductive inference by GDR mathematicians--A survey. Inf. Sc~ 22, 149-169.
	86	KNong, B., ANO KNOSR, K. 1976. A method for inferring context-free grammars. In{. Control 31, 129-146.
	87	KODRATOFF, Y. 1979. A class of functions synthesized from a finite number of examples and a LISP program scheme. Int. J. Comput. Inf. Sci. 8, 489-521.
	88	KODRATOFF, Y., ANn FARGUES, J. 1978. A sane algorithm for the synthesis of LISP functions from example problems. In Proceedings of the AISB/ G~ Conference on Artificial Intelligence (Hamburg, July). Society for the Study of Artificial Intelligence and Simulation of Behavior/Gesellschaft for informatik, pp. 169-175.
	89	KOLMOGOROV, A. N. 1965. Three approaches to the quantitative definition of information. ProbL In/. Transm. 1, 1-7.
	90	KUOEL, P. 1977. Induction, pure and simple. Inf. Control 35, 276-336.
	91	LAUOAN, L. 1977. Progress and Its Problems. University of California Press, Berkeley, Calif.
	92	LEV~NE, B. 1981. Derivatives of tree sets with applications to grammatical inference. IEEE Trans. Pattern Anal. Mach. lntell. PAMI-3, 285-293.
	93	L~VlNE, B. 1982. The use of tree derivatives and a sample support parameter for inferring tree systerns. IEEE Trans. Pattern Anal. Mach. InteU. PAM{-4, 25-34.
	94	LINONER, R. 1972. Algorithmische Erkennung. Ph.D. dissertation, Friedrich-Schiller-Universitat, Jena, G.D.R.
	95	Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
	96	M~TIN-LOF, P. 1966. The definition of random sequences. Inf. Control 9, 602--619.
	97	M~TIN-LOF, P. 1971. Complexity oscillations in infinite binary strings. Z. Wahrscheinlichkeitstheor. Verw. Geb. 19, 225-230.
	98	MARYANSKI, F. J., AND BOOTH, T. L. 1977. Inference of finite-state probabilistic grammars. IEEE Trans. Comput. C-26, 521-536.
	99	MICHALSKI, R. 1980. Pattern recognition as rule guided inductive inference. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-2, 349-361.
	100	MICHALSKi, R., CARBONELL, J., ANO MITCHELL, T., Eds. 1983. Machine Learning. Tioga Publ., Palo Alto, Calif.
	101	MICLET, L. 1980. Regular inference with a tail-clustering method. IEEE Tram. Syst. Man Cybern. SMC- 10, 737-743.
	102	MINICOZZl, E. 1976. Some natural properties of strong identification in inductive inference. Theor. Comput. ScL 2, 345-360.
	103	MITCHELL, T. M. 1982. Generalization as search. Arti{. IntelL 18, 203-226.
	104	NIx, R. 1983. Editing by example. Ph.D. dissertation, Computer Science Dept., Yale University, New Haven, Conn.
	105	Robert Nix, Editing by example, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.186-195, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800530]
	106	OSHERSON, D. N., AND WEiNSTEIN, $. 1982. Criteria of language learning. Inf. Control 52, 123-138.
	107	PAo, T. W., AND CARR, J. W., III. 1978. A solution of the syntactical induction-inference problem for regular languages. Comput. Lang. 3, 53-64.
	108	PERSSON, S. 1966. Some sequence extrapolating programs: A study of representation and modeling in inquiring systems. Ph.D. dissertation, Computer Science Dept., Stanford University, Stanford, Calif.
	109	PIVAR, M., AND FINKELSTEIN, M. 1964. Automation, using LISP, of inductive inference on sequences. In The Programming Language LISP, Berkey, Ed. M.I.T. Press, Cambridge, Mass., pp. 125-136.
	110	PIVAR, M., ANO GOAD, E. 1964. The LISP program for inductive inference on sequences. In The Programming Language LISP, Berkey, Ed. M.I.T. Press, Cambridge, Mass., pp. 260-289.
	111	PLOTKI~, G. D. 1970. A note on inductive generalization, in Machine intelligence 5. Elsevier North- Holland, New York, pp. 153-163.
	112	PLOTKIN, G. D. 1971a. Automatic methods ofinductive inference. Ph.D. dissertation, Computer Science Dept., Edinburgh University.
	113	PLOTKm, G. D. 1971b. A further note on inductive generalization. In Machine Intelligence 6. Elsevier Notch-Holland, New York, pp. 101-124.
	114	PODN}EgS, K. M. 1974. Comparing various concepts of function prediction, Part {. LaW. Gosudar~t. Univ. Uch. Zapiski 210, 68-81 (in Russian).
	115	PODNIEKS, K. M. 1975a. Probabilistic synthesis of enumerated classes of functions. Sou. Math. Doki. 16, 1042-1045.
	116	POON{EKS, K. M. 19751). Comparing various concepts of function prediction, Part II. LaW. Gosudarst. Univ. Uch. Zapiski 233, 33-44. (in Russian).
	117	PUTNAM, H. 1975. Probability and confirmation. In Mathematics, Matter and Method. Cambridge Univ. Press, Cambridge, England.
	118	REYNOLDS, J. C. 1970. Transformational systems and the algebraic structure of atomic formulas. In Machine Intelligence 5. Elsevier North-Holland, New York, pp. 135-151.
	119	SHAPIRO, E. 1981a. Inductive inference of theories from facts. Tech. Rep. 192, Dept. of Computer Science, Yale University, New Haven, Conn.
	120	SnAPmO, E. 1981b. A general incremental algorithm that infers theories from facts. In Proceedings o{ ~he 7th International Joint Conference on Artificial Intelligence (Vancouver, B.C., Canada, Aug.). international Joint Council on Artificial Intelligence, pp. 446-451.
	121	Ehud Y. Shapiro, Algorithmic program diagnosis, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.299-308, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582185]
	122	Ehud Yehuda Shapiro, Algorithmic program debugging, 1982
	123	SHAW, D., SWARTOUT, W., AND GREEN, C. 1975. inferring LISP programs from example problems. In Proceedings o{ the 4th International Joint Con- /erence on Artificial Intelligence (Tibilsi, Georgia, USSR, Sept.). International Joint Council on Artificial Intelligence, pp. 260-267.
	124	Takeshi Shinohara, Polynomial Time Inference of Extended Regular Pattern Languages, Proceedings of RIMS Symposium on Software Science and Engineering, p.115-127, January 1983
	125	SHINOHARA, T. 1982b. Polynomial time inference of pattern languages and its applications. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science.
	126	SmLoss~, L., ANo SYKES, D. 1975. Automatic program synthesis for example problems. In Proceedings o{ the 4th International Joint Con{erence on Artificial Intelligence (Tibilsi, Georgia, USSR, Sept.). International Joint Council on Artificial Intelligence, pp. 268-273.
	127	SIMON, H. A., A~O KOTOVSK~, K. 1963. Human acquisition of concepts for sequential patterns. Psych. Rev. 70, 534-546.
	128	Carl H. Smith, The Power of Pluralism for Automatic Program Synthesis, Journal of the ACM (JACM), v.29 n.4, p.1144-1165, Oct. 1982 [doi>10.1145/322344.322356]
	129	SMITH, D. R. 1982. A survey of the synthesis of LISP programs from examples. In Automatic Program Construction Techinques, A. W. Biermann, G. Guiho, and Y. Kodratoff, Eds. Macmillan, New York.
	130	SOLOMONOFF, R. J. 1964. A formal theory of inductive inference. In{. Control 7, 1-22, 224-254.
	131	SOLOMONOFF, R. J. 1975. Inductive inference theory--A unified approach to problems in pattern recognition and artificial intelligence. In Proceedings o{ the 4th International Con{erence Artificial Intelligence (Tibilsi, Georgia, USSR, Sept.). international Joint Council on Artificial Intelligence, pp. 274-280.
	132	SOLOMONOFF, R. J. 1978. Complexity.based induction systems: comparisons and convergence theorems. IEEE Trans. in{. Theor. IT-24, 422-432.
	133	Salvatore Joseph Stolfo, Automatic discovery of heuristics for nondeterministic programs from sample execution traces, 1979
	134	STOLFO, S. J., AND HARRISON, M. C. 1979. Automatic discovery of heuristics for nondeterministlc programs. Tech. Pep. 7, Computer Science Dept., New York University.
	135	Phillip Dale Summers, Program construction from examples., 1975
	136	Phillip D. Summers, A Methodology for LISP Program Construction from Examples, Journal of the ACM (JACM), v.24 n.1, p.161-175, Jan. 1977 [doi>10.1145/321992.322002]
	137	THIELE, H. 1973. Lernverfahren zur Erkennung formaler Sprachen. Kyberr~ Forsch. 3, 11-93.
	138	TH{ELP., H. 1975. Zur Charakterisierung yon grkennungssytemen mit einbettendem Konvergenzbegriff. Kornpliziertheit Lern Erkennungsprozessen 2. 188--207. Jena, G.D.R.
	139	VAN DER MUDE, A., AND WALKER, A. 1978. On the inference of stochastic regular grammars. Inf. Control 38, 310-329.
	140	VEELENTURF, L. P. J. 1978. Inference of sequential machines from sample computations. IEEE Trans. Comput. C-27, 167-170.
	141	VERE, S. A. 1980. Multilevel counterfactuals for generalizations of relational concepts and productions. Artif {ntell~ I4, 139-164.
	142	VERE, S. A. 1981. Constrained N-to-1 generalization. Preprint, Jet Propulsion Laboratory, Pasadena, Calif.
	143	WATANA~E, S. 1960. Information-theoreticalaspects of inductive and deductive inference. IBM J. Res. Devel. 4, 208-231.
	144	WATERMAN, D. A., FAUGHT, W. S., KLAHR, P., RO- SENSCHEIN, $. J., AND WESSON, R. 1980. Design issues for exemplary programming. Tech. Rep. N-1484-RC, Rand Corporation, Santa Monica, Calif.
	145	WEXLER, K., AND CULtCOVER, P. 1980. Formal Principles of Language Acquisition. M.I.T. Press, Cambridge, Mass.
	146	WHARTON, R. M. 1974. Approximate language identification. Inf. Control 26, 236-255.
	147	WHARTOn, R. M. 1977. Grammar enumeration and inference. Inf. Control 33, 253-272.
	148	WIEHAGEN, R. 1976. Limes-erkennung rekursiver Funktionen durch spezielle Stratigen. Elektron. lnforma~ionsverarbeit. Kybern. (ELK) 12, 93-99.
	149	W{~.HAGEN, R. 1977. Identification of formal languages. In Lecture Notes in Computer Science, vol. 53. Springer-Verlag, New York, pp. 571-579.
	150	Rolf Wiehagen, Characterization Problems in the Theory of Inductive Inference, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.494-508, July 17-21, 1978
	151	WIEHA(~EN, R., A~O L}~.PE, W. 1976. Charakteristche Eigenschaften yon erkennbaren Klassen rekursiver Funktionen. Elektrotr Inforrna. tionsverarbeit. Kybern. (EIK) 12, 421-438.
	152	WINSTON, P. 1975. Learning Structural Descriptions from Examples. McGraw-Hill, New York.
	153	ZLOOF, M. 1977. Query-by-Example: A data base language. IBM Syst. J. 16, 324-343.
	154	ZVO~KtN, A. K., A~D LP.v{N, L. A. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Rev. 25, 83-124.

CITED BY 102

	Thomas Zeugmann , Sandra Zilles, Learning recursive functions: A survey, Theoretical Computer Science, v.397 n.1-3, p.4-56, May, 2008
	Jonathan E. Cook , Alexander L. Wolf, Automating process discovery through event-data analysis, Proceedings of the 17th international conference on Software engineering, p.73-82, April 24-28, 1995, Seattle, Washington, United States
	Steffen Lange , Thomas Zeugmann, Types of monotonic language learning and their characterization, Proceedings of the fifth annual workshop on Computational learning theory, p.377-390, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Rūsiņš Freivalds , Carl H. Smith, On the role of procrastination for machine learning, Proceedings of the fifth annual workshop on Computational learning theory, p.363-376, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Dana Angluin, Computational learning theory: survey and selected bibliography, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.351-369, May 04-06, 1992, Victoria, British Columbia, Canada
	Efim Kinber , Frank Stephan, Language learning from texts (extended abstract): mind changes, limited memory and monotonicity, Proceedings of the eighth annual conference on Computational learning theory, p.182-189, July 05-08, 1995, Santa Cruz, California, United States
	Klaus P. Jantke, Case-based learning in inductive inference, Proceedings of the fifth annual workshop on Computational learning theory, p.218-223, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	Tom Moher , Andrew Johnson , Stellan Ohlsson , Mark Gillingham, Bridging strategies for VR-based learning, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.536-543, May 15-20, 1999, Pittsburgh, Pennsylvania, United States
	Efim Kinber , Christophe Papazian , Carl Smith , Rolf Wiehagen, On the intrinsic complexity of learning recursive functions, Proceedings of the twelfth annual conference on Computational learning theory, p.257-266, July 07-09, 1999, Santa Cruz, California, United States
	Rūsiņš Freivalds , Efim Kinber , Carl H. Smith, On the impact of forgetting on learning machines, Journal of the ACM (JACM), v.42 n.6, p.1146-1168, Nov. 1995
	Paul A. Fishwick, Fuzzy set methods for qualitative and natural language oriented simulation, Proceedings of the 22nd conference on Winter simulation, p.513-519, December 09-12, 1990, New Orleans, Louisiana, United States
	Rūsiņš Freivalds , Efim Kinber , Carl H. Smith, On the impact of forgetting on learning machines, Proceedings of the sixth annual conference on Computational learning theory, p.165-174, July 26-28, 1993, Santa Cruz, California, United States
	Rūsiņš Freivalds , Marek Karpinski , Carl H. Smith, Co-learning of total recursive functions, Proceedings of the seventh annual conference on Computational learning theory, p.190-197, July 12-15, 1994, New Brunswick, New Jersey, United States
	Erkki Mäkinen , Tarja Systä, MAS — an interactive synthesizer to support behavioral modelling in UML, Proceedings of the 23rd International Conference on Software Engineering, p.15-24, May 12-19, 2001, Toronto, Ontario, Canada
	Shai Ben-David, Can finite samples detect singularities of real-valued functions?, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.390-399, May 04-06, 1992, Victoria, British Columbia, Canada
	D. L. Maulsby , I. H. Witten, Inducing programs in a direct-manipulation environment, ACM SIGCHI Bulletin, v.20 n.SI, p.57-62
	John R. Clymer, System design and evaluation using discrete event simulation with artificial intelligence, Proceedings of the 25th conference on Winter simulation, p.1347-1356, December 12-15, 1993, Los Angeles, California, United States
	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984
	Sanjay Jain , Carl Smith , Rolf Wiehagen, On the power of learning robustly, Proceedings of the eleventh annual conference on Computational learning theory, p.187-197, July 24-26, 1998, Madison, Wisconsin, United States
	Thomas Ellman, Explanation-based learning: a survey of programs and perspectives, ACM Computing Surveys (CSUR), v.21 n.2, p.163-221, Jun. 1989
	Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998
	Kalvis Apsītis , Rūsiņš Freivalds , Carl H. Smith, On the inductive inference of real valued functions, Proceedings of the eighth annual conference on Computational learning theory, p.170-177, July 05-08, 1995, Santa Cruz, California, United States
	William I. Gasarch , Andrew C. Y. Lee, Inferring answers to queries, Proceedings of the tenth annual conference on Computational learning theory, p.275-284, July 06-09, 1997, Nashville, Tennessee, United States
	Susanne Kaufmann , Frank Stephan, Resource bounded next value and explanatory identification: learning automata, patterns and polynomials on-line, Proceedings of the tenth annual conference on Computational learning theory, p.263-274, July 06-09, 1997, Nashville, Tennessee, United States
	Douglas A. Cenzer , William R. Moser, Inductive inference of functions on the rationals, Proceedings of the eighth annual conference on Computational learning theory, p.178-181, July 05-08, 1995, Santa Cruz, California, United States
	L. Pitt, Probabilistic inductive inference, Journal of the ACM (JACM), v.36 n.2, p.383-433, April 1989
	David L. Maulsby , Ian H. Witten , Kenneth A. Kittlitz, Metamouse: specifying graphical procedures by example, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.127-136, July 1989
	John Case , Sanjay Jain , Arun Sharma, On learning limiting programs, Proceedings of the fifth annual workshop on Computational learning theory, p.193-202, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Ganesh R. Baliga , John Case , Sanjay Jain, Synthesizing enumeration techniques for language learning, Proceedings of the ninth annual conference on Computational learning theory, p.169-180, June 28-July 01, 1996, Desenzano del Garda, Italy
	Andris Ambainis, Probabilistic and team PFIN-type learning: general properties, Proceedings of the ninth annual conference on Computational learning theory, p.157-168, June 28-July 01, 1996, Desenzano del Garda, Italy
	Rusins Freivalds , Marek Karpinski , Carl H. Smith , Rolf Wiehagen, Learning by the process of elimination, Information and Computation, v.176 n.1, p.37-50, July 2002
	B. K. Natarajan, On learning Boolean functions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.296-304, January 1987, New York, New York, United States
	Andrey Burago, Learning structurally reversible context-free grammars from queries and counterexamples in polynomial time, Proceedings of the seventh annual conference on Computational learning theory, p.140-146, July 12-15, 1994, New Brunswick, New Jersey, United States
	Rolf Wiehagen , Carl H. Smith, Generalization versus classification, Proceedings of the fifth annual workshop on Computational learning theory, p.224-230, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Sanjay Jain , Efim Kinber , Rolf Wiehagen , Thomas Zeugmann, On learning of functions refutably, Theoretical Computer Science, v.298 n.1, p.111-143, 4 April 2003
	Sanjay Jain , Arun Sharma, Hypothesis formation and language acquisition with an infinitely-often correct teacher, Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge, March 04-07, 1990, Pacific Grove, California
	Sanjay Jain , Efim Kinber , Christophe Papazian , Carl Smith , Rolf Wiehagen, On the intrinsic complexity of learning recursive functions, Information and Computation, v.184 n.1, p.45-70, July 10, 2003
	Frank Stephan , Thomas Zeugmann, Learning classes of approximations to non-recursive functions, Theoretical Computer Science, v.288 n.2, p.309-341, 16 October 2002
	Steffen Lange , Gunter Grieser , Klaus P. Jantke, Advanced elementary formal systems, Theoretical Computer Science, v.298 n.1, p.51-70, 4 April 2003
	Dana Ron , Ronitt Rubinfeld, Exactly Learning Automata of Small Cover Time, Machine Learning, v.27 n.1, p.69-96, April 1997
	Wolfgang Merkle , Frank Stephan, Trees and learning, Journal of Computer and System Sciences, v.68 n.1, p.134-156, February 2004
	John Case , Sanjay Jain , Frank Stephan , Rolf Wiehagen, Robust learning: rich and poor, Journal of Computer and System Sciences, v.69 n.2, p.123-165, September 2004
	Stanley F. Chen, Bayesian grammar induction for language modeling, Proceedings of the 33rd annual meeting on Association for Computational Linguistics, p.228-235, June 26-30, 1995, Cambridge, Massachusetts
	W. M. P. van der Aalst , A. J. M. M. Weijters, Process mining: a research agenda, Computers in Industry, v.53 n.3, p.231-244, April 2004
	Rajeev Alur , Kousha Etessami , Mihalis Yannakakis, Inference of message sequence charts, Proceedings of the 22nd international conference on Software engineering, p.304-313, June 04-11, 2000, Limerick, Ireland
	P. Smyth , R. M. Goodman, An Information Theoretic Approach to Rule Induction from Databases, IEEE Transactions on Knowledge and Data Engineering, v.4 n.4, p.301-316, August 1992
	Wolfgang Merkle , Frank Stephan, Trees and learning, Proceedings of the ninth annual conference on Computational learning theory, p.270-279, June 28-July 01, 1996, Desenzano del Garda, Italy
	Rajeev Alur , Kousha Etessami , Mihalis Yannakakis, Inference of Message Sequence Charts, IEEE Transactions on Software Engineering, v.29 n.7, p.623-633, July 2003
	William I. Gasarch , Carl H. Smith, Learning via queries, Journal of the ACM (JACM), v.39 n.3, p.649-674, July 1992
	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988
	Andris Ambainis, Probabilistic inductive inference: a survey, Theoretical Computer Science, v.264 n.1, p.155-167, 08/06/2001
	Mark Burgin , Allen Klinger, Experience, generations, and limits in machine learning, Theoretical Computer Science, v.317 n.1-3, p.71-91, June 4, 2004
	Peter Kugel, Toward a theory of intelligence, Theoretical Computer Science, v.317 n.1-3, p.13-30, June 4, 2004
	Margaret Francel , David J. John, An algorithm for constructing an even grammar from a language sample, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama
	Ronald L. Rivest , Robert Sloan, A new model for inductive inference, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	Gabriel Valiente, Are complete K-trees something more than decision trees?, ACM SIGART Bulletin, v.2 n.2, p.6, April 1991
	Muffy Calder , Evan Magill , Stephan Reiff-Marganiec , Vijeyananthan Thayananthan, Theory and practice of enhancing a legacy software system, Systems engineering for business process change: new directions, Springer-Verlag New York, Inc., New York, NY, 2002
	Sanjay Jain , Frank Stephan, Learning how to separate, Theoretical Computer Science, v.313 n.2, p.209-228, 17 February 2004
	Claudia Crimi , Angela Guercio , Giuliano Pacini , Genoveffa Tortora , Maurizio Tucci, Automating Visual Language Generation, IEEE Transactions on Software Engineering, v.16 n.10, p.1122-1135, October 1990
	P. García , E. Vidal, Inference of k-Testable Languages in the Strict Sense and Application to Syntactic Pattern Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.9, p.920-925, September 1990
	Wil van der Aalst , Ton Weijters , Laura Maruster, Workflow Mining: Discovering Process Models from Event Logs, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1128-1142, September 2004
	L. F. Fass, Learnability of CFLs: inferring syntactic models from constituent structure, ACM SIGART Bulletin
	Jonathan E. Cook , Zhidian Du , Chongbing Liu , Alexander L. Wolf, Discovering models of behavior for concurrent workflows, Computers in Industry, v.53 n.3, p.297-319, April 2004
	Jonathan E. Cook , Zhidian Du, Discovering thread interactions in a concurrent system, Journal of Systems and Software, v.77 n.3, p.285-297, September 2005
	Sandra Zilles, Increasing the power of uniform inductive learners, Journal of Computer and System Sciences, v.70 n.4, p.510-538, June 2005
	J. Oncina , P. García , E. Vidal, Learning Subsequential Transducers for Pattern Recognition Interpretation Tasks, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.5, p.448-458, May 1993
	Steffen Lange , Jochen Nessel, Decision lists over regular patterns, Theoretical Computer Science, v.298 n.1, p.71-87, 4 April 2003
	Daniel Reidenbach, A non-learnable class of E-pattern languages, Theoretical Computer Science, v.350 n.1, p.91-102, 18 January 2006
	Raymond Kosala , Hendrik Blockeel , Maurice Bruynooghe , Jan Van den Bussche, Information extraction from structured documents using k-testable tree automaton inference, Data & Knowledge Engineering, v.58 n.2, p.129-158, August 2006
	R. Freivalds , R. F. Bonner, Quantum inductive inference by finite automata, Theoretical Computer Science, v.397 n.1-3, p.70-76, May, 2008
	Andrew C. Lee, Learning via finitely many queries, Annals of Mathematics and Artificial Intelligence, v.44 n.4, p.401-418, August 2005
	Marcus Hutter, Optimality of universal Bayesian sequence prediction for general loss and alphabet, The Journal of Machine Learning Research, 4, p.971-1000, 12/1/2003
	David M. Dutton , Gerard V. Conroy, A review of machine learning, The Knowledge Engineering Review, v.12 n.4, p.341-367, December 1997
	Ulrik Schroeder , Arno Spinner, ALIEN: a programming environment generator for personal computers, Proceedings of the 1988 ACM SIGSMALL/PC symposium on ACTES, p.45-52, May 04-06, 1988, Cannes, France
	Margaret Francel , David J. John, Constructing an even grammar from a 2-element sample, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
	Stefan C. Kremer, Spatiotemporal Connectionist Networks: A Taxonomy and Review, Neural Computation, v.13 n.2, p.249-306, February 2001
	Geert Jan Bex , Frank Neven , Thomas Schwentick , Karl Tuyls, Inference of concise DTDs from XML data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Sandra Zilles, An approach to intrinsic complexity of uniform learning, Theoretical Computer Science, v.364 n.1, p.42-61, 2 November 2006
	Thomas Zeugmann, From learning in the limit to stochastic finite learning, Theoretical Computer Science, v.364 n.1, p.77-97, 2 November 2006
	Andris Ambainis, Probabilistic and team PFIN-type learning: General properties, Journal of Computer and System Sciences, v.74 n.4, p.457-489, June, 2008
	Bala Kalyanasundaram , Mahe Velauthapillai, Capabilities of Thoughtful Machines, Fundamenta Informaticae, v.74 n.2,3, p.329-340, August 2006
	A. K. Medeiros , A. J. Weijters , W. M. Aalst, Genetic process mining: an experimental evaluation, Data Mining and Knowledge Discovery, v.14 n.2, p.245-304, April 2007
	Paul Helman , Rebecca Gore, Prioritizing Information for the Discovery of Phenomena, Journal of Intelligent Information Systems, v.11 n.2, p.99-138, Sept./Oct. 1998
	Takashi Yokomori , Satoshi Kobayashi, Learning Local Languages and Their Application to DNA Sequence Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.10, p.1067-1079, October 1998
	William I. Gasarch , Andrew C. Y. Lee, Inferring answers to queries, Journal of Computer and System Sciences, v.74 n.4, p.490-512, June, 2008
	Jānis Bārzdiņš , Rūsiņš Freivalds , Carl H. Smith, Learning with belief levels, Journal of Computer and System Sciences, v.74 n.4, p.527-545, June, 2008
	Geert Jan Bex , Wouter Gelade , Frank Neven , Stijn Vansummeren, Learning deterministic regular expressions for the inference of schemas from XML data, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Bala Kalyanasundaram , Mahendran Velauthapillai, Taming teams with mind changes, Journal of Computer and System Sciences, v.74 n.4, p.513-526, June, 2008
	David L. Maulsby , Ian H. Witten , Kenneth A. Kittlitz , Valerio G. Franceschin, Inferring graphical procedures: the compleat metarnouse, Human-Computer Interaction, v.7 n.1, p.47-89, March 1992
	Peter Manolios , Robert Fanelli, First-order recurrent neural networks and deterministic finite state automata, Neural Computation, v.6 n.6, p.1155-1173, November 1994
	Anirban Dasgupta , Ravi Kumar , Amit Sasturkar, De-duping URLs via rewrite rules, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Armando Solar-Lezama , Christopher Grant Jones , Rastislav Bodik, Sketching concurrent data structures, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Sanjay Jain, On some open problems in reflective inductive inference, Information Processing Letters, v.109 n.3, p.208-211, January, 2009
	Lijie Wen , Jianmin Wang , Wil M. Aalst , Biqing Huang , Jiaguang Sun, A novel approach for process mining based on event types, Journal of Intelligent Information Systems, v.32 n.2, p.163-190, April 2009
	Sanjay Jain , Frank Stephan , Nan Ye, Prescribed learning of r.e. classes, Theoretical Computer Science, v.410 n.19, p.1796-1806, April, 2009
	Neil Walkinshaw , Kirill Bogdanov , Mike Holcombe , Sarah Salahuddin, Improving dynamic software analysis by applying grammar inference principles, Journal of Software Maintenance and Evolution: Research and Practice, v.20 n.4, p.269-290, July 2008
	Lu Ruqian , Liu Yinghui , Li Xiaobin, Computer-aided grammar acquisition in the Chinese understanding system CUSAGA, Proceedings of the 11th international joint conference on Artificial intelligence, p.1550-1555, August 20-25, 1989, Detroit, Michigan
	T. Gergely , Z. S. Szabo, Inductive inference on the base of fixed point theory, Proceedings of the 10th international joint conference on Artificial intelligence, p.932-938, August 23-28, 1987, Milan, Italy
	James P. Delgrande, A formal approach to learning from examples, Proceedings of the 10th international joint conference on Artificial intelligence, p.315-322, August 23-29, 1987, Milan, Italy
	L. G. Valiant, Learning disjunction of conjunctions, Proceedings of the 9th international joint conference on Artificial intelligence, p.560-566, August 18-23, 1985, Los Angeles, California
	Stijn Goedertier , David Martens , Jan Vanthienen , Bart Baesens, Robust Process Discovery with Artificial Negative Events, The Journal of Machine Learning Research, 10, p.1305-1340, June 2009