article

Free access

Inductive Inference: Theory and Methods

Authors:

Dana Angluin,

Carl H. SmithAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 15, Issue 3

Pages 237 - 269

https://doi.org/10.1145/356914.356918

Published: 01 September 1983 Publication History

PDF eReader

References

[1]

ADELMAN, L., AND BLUM, M. 1975. Inductive inference and unsolvabiIity. Tech. Rep., Electrical Engineering and Computer Science Dept., Univ. of Calif., Berkeley.

Google Scholar

[2]

AN6LUIN, D. 1978. On the complexity of minimum inference of regular sets. Inf. Control 39, 337-350.

Google Scholar

[3]

ANCLUlN, D. 1980a. Inductive inference of formal languages from positive data. In{. Control 45, 117- 135.

Google Scholar

[4]

ANGLUIN, D. 1980b. Finding patterns common to a set of strings. J. Cornput. Syst. Sci. 21, 46-62.

Google Scholar

[5]

ANGLUIN, D. 1982a. A note on the number of queries needed to identify regular languages. In{. Control 51, 76-87.

Google Scholar

[6]

ANGLVtN, D. 1982b. Inference of reversible languages. J. ACM 29, 3 (July), 741-765.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[9]

BARZm~, J. M. 1974b. Two theorems on the limiting synthesis of functions. Latv. Gos. Univ. Uch. Zapiski 210, 82-88 (in Russian).

Google Scholar

[10]

B~zI~I~, J. M., ANO FREIVALD, R. V. 1972. On the prediction of general recursive functions. Soy. Math. Dokl I3, 1224-1228.

Google Scholar

[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.

Google Scholar

[12]

BERGER, J., AND PAIR, C. 1978. Inference for regular bilanguages. J. Comput. Sys. Sci. 16, 100-122.

Google Scholar

[13]

BIERMANN, A. W. 1972. On the inference of Turing machines from sample computations. Arti{. Intell. 3, 181-198.

Google Scholar

[14]

BIERMANN, A. W. 1975. The inference of regular LISP programs from examples. IEEE Trans. Syst. Man Cybern. SMC-8, 585-600.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[17]

BIERMANN, A. W., AND KRISHNASWAMY, R. 1976. Constructing programs from example computations. IEEE Trans. Sofiw. Eng. SE-2, 141-153.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[20]

BLUM, L., AND BLUM, M. 1975. Toward a mathematical theory of inductive inference. Inf. Control 28, 125-155.

Google Scholar

[21]

BLUM, M. 1967a. On the size of machines. In{. Control 11, 257-265.

Google Scholar

[22]

BLUM, M. 1967b. A machine-independent theory of the complexity of recursive functions. J. ACM 14, 2 (Apr.) 322-336.

Crossref

Google Scholar

[23]

BRANDT, U. 1981. A characterization of identifiable sets. Preprint, Technische Hochschule Darmstadt, F.R.G.

Google Scholar

[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.

Google Scholar

[25]

BUCHANAN, B. G., AND FEIGENBAUM, E. A. 1978. Dendral and Meta-Dendral: Their applications dimension. Artif lnteU. 11, 5-24.

Google Scholar

[26]

BUNDY, A., AND SILVER, B. 1981. A critical survey of rule learning programs. Tech. Rep. 169, Dept. of Artificial Intelligence, Edinburgh Univ.

Google Scholar

[27]

CAS~., J., Argo LVNrS, C. 1982. inductive inference and language identification. In Proceedings of the International Colloquium on Algorithms, Languages, and Programming (ICALP) 82, (Barcelona, Spain; June). Springer-Verlag, New York, pp. 107-115.

Crossref

Google Scholar

[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.

Google Scholar

[29]

CASE, J., AND SMITH, C. 1978. Anomaly hierarchies of mechanized inductive inference. In Proceedings of the l Oth A CM Symposium on Theory of Computing (San Diego, Calif., May 1-3). ACM, New York, pp. 314-319.

Crossref

Google Scholar

[30]

CASE, J., A~D SMrrH, C. 1983. Comparison of identification criteria for machine inductive inference. Theor. Comput. Sci. 25, 193-220.

Google Scholar

[31]

CH^ITIN, G. J. 1974~ Information-theoretic limitations of formal systems. J. ACM 21, 3 (July), 403- 424.

Crossref

Google Scholar

[32]

CHAiTIN, G. J. 1975. A theory of program size formally identical to information theory. J~ ACM 22, 3 (July) 329-340.

Crossref

Google Scholar

[33]

CHAITIN, G. J. 1976. Information-theoretic characterizations of recursive infinite strings. Theor. Comput. ScL 2, 45-48.

Google Scholar

[34]

CnEN, K. J. 1982. Tradeoffs in the inductive inference of nearly minimal size programs. Int. Control 52, 68-86.

Google Scholar

[35]

COOK, C. M., ROSENFELD, A., AND ARONSON, A. R. 1976. Grammatical inference by hill-climbing. In{. Sci. 10, 59-80.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[40]

CRESPI-REGHIZZ{, S., MELKANOFF. M. A, AND LICH- TEN, L. 1973. The use of gra~',. ~tical inference for designing programming languages. Commun. ACM 16, 2 (Feb.), 83-90.

Crossref

Google Scholar

[41]

CsESpJ-REGmzzl, S., GwoA, G., AND MA~DmOU, D. 1978. Noncounting context-free languages. J. ACM 25, 4 (Oct.), 571-580.

Crossref

Google Scholar

[42]

DALEY, R. 1973. An example of information and computation resource trade-off. J. A CM 20, 4 (Oct.), 687-695.

Crossref

Google Scholar

[43]

DALP. Y, R. 1977. On the inference of optimal descriptions. Theor. Comput. Sci. 4, 301-319.

Google Scholar

[44]

DALE~, R. 1983. On the error correcting power of pluralism in inductive inference. Theor. Comput. Sci. 24, 95-104.

Google Scholar

[45]

DALE~, R., AND SMITH, C. 1983. On the complexity of inductive inference. Tech. Pep. 83-4, Dept. of Computer Science, Univ. of Pittsburgh.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[48]

DOUCET, P. G. 1974. The syntactic inference problem for D0L sequences. In L-Systems, G. Rozenberg and A. Salomaa, Eds. Springer Lecture Notes on Computer Science, vol. 15. Springer- Verlag, New York, pp. 146-161.

Crossref

Google Scholar

[49]

FELDMAN, J. A. 1967. First thoughts on grammatical inference. Tech. Rep., Computer Science Dept., Artificial Intelligence Memo 55, Stanford UniversiW, Stanford, Calif.

Google Scholar

[50]

FELt)MAN, J. A. 1972. Some decidability results in grammatical inference. In{. Control 20, 244-262.

Google Scholar

[51]

FELOMAN, J. A., AND SmELOS, P. 1977. Total complexity and the inference of best programs. Math. $yst. Theory. 10, 181-191.

Google Scholar

[52]

FELDMAN, J. A., GIPS, J., HORmNa, J. J., A~o REDER, S. 1969. Grammatical complexity and inference. Tech. Rep., Computer Science Dept., Stanford Univ., Stanford, Calif.

Crossref

Google Scholar

[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.

Google Scholar

[54]

FLANAGAN, P. A. 1981. A discrete model of semantic learning. Tech. Rep. CS-79, Computer Science Dept., Brown University, Providence, R. I.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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).

Google Scholar

[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.

Google Scholar

[60]

FREIVALO, R. V., AND WIEHAOEN, R. 1979. Inductive inference with additional information. E/ectron. Informationsverarb. Kybern. (EIK) 18, 179- 185.

Google Scholar

[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.

Google Scholar

[62]

FRIEDBERG, R, 1958. Three theorems on recursive enumeration. J. Symb. Logic 23, 309-316.

Google Scholar

[63]

Fu, K. S. 1975. Syntactic Methods in Pattern Recognition. Academic Press, New York.

Google Scholar

[64]

Fu K. S. 1977. Syntactic Pattern Recognition, Applications. Springer-Verlag, New York.

Google Scholar

[65]

Fu, K. S. 1982. Syntactic Pattern Recognition and Applications. Prentice-Hall, New York.

Google Scholar

[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.

Google Scholar

[67]

GACS, P. 1983. On the relationship between descriptional complexity and algorithmic probability. Theor. Comput. ScL, 22, 1, 2, 71-93.

Google Scholar

[68]

GAINES, B. R. 1976. Behavior/structure transformations under uncertainty. Int. J. Man-Math. Stud. 8, 337-365.

Google Scholar

[69]

GAINES, B. R. 1978. Maryanski's grammatical inferencer. IEEE Trans. Comput. C-28, 62-64.

Google Scholar

[70]

GOLD, E. M. 1967. Language identification in the limit. Inf. Control lO, 447-474.

Google Scholar

[71]

GOLD, E. M. 1972. System identification via state characterization. AuWmatica 8, 621-636.

Google Scholar

[72]

GOLD, E. M. 1978. Complexity of automaton identification from given data. Inf. Control. 37, 302- 320.

Google Scholar

[73]

GONZALEZ, R. C., A~D TnOMASON, M. G. 1978. Syntactic Pattern Recognition, An Introduction. Addison-Wesley, Reading, Mass.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[76]

HAYES-RO?H, F., AND McDERMOTT, J. 1978. An interference matching technique for inducing abstractions. Comrnun. ACM 21, 5 (May), 401-411.

Crossref

Google Scholar

[77]

HOP, NING, J. J. 1969. A study of grammatical inference. Ph.D. dissertation, Computer Science Dept., Stanford Univ., Stanford, Calif.

Google Scholar

[78]

JANTKE, K. P. 1979. Natural properties of strategies identifying recursive functions. Elektron. In{ormationsverarb. Kybern. (EIK) 15, 487-496.

Google Scholar

[79]

JANTKE, K. P., AND BEICK, H. R. 1981. Combining postulates of naturalness in inductive inference. Elektron. Informationsverarb. Kybern. (ELK) 17, 465-484.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[84]

JUNG, H. 1977. Zur Untersuchung yon abstrakten interaktiven Erkennungssystemen. Ph.D. dissertation, Humbolt University, Berlin, GDR.

Google Scholar

[85]

KLETTE, R., AND WIEHAGEN, R. 1980. Research in the theory of inductive inference by GDR mathematicians--A survey. Inf. Sc~ 22, 149-169.

Google Scholar

[86]

KNong, B., ANO KNOSR, K. 1976. A method for inferring context-free grammars. In{. Control 31, 129-146.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[89]

KOLMOGOROV, A. N. 1965. Three approaches to the quantitative definition of information. ProbL In/. Transm. 1, 1-7.

Google Scholar

[90]

KUOEL, P. 1977. Induction, pure and simple. Inf. Control 35, 276-336.

Google Scholar

[91]

LAUOAN, L. 1977. Progress and Its Problems. University of California Press, Berkeley, Calif.

Google Scholar

[92]

LEV~NE, B. 1981. Derivatives of tree sets with applications to grammatical inference. IEEE Trans. Pattern Anal. Mach. lntell. PAMI-3, 285-293.

Google Scholar

[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.

Google Scholar

[94]

LINONER, R. 1972. Algorithmische Erkennung. Ph.D. dissertation, Friedrich-Schiller-Universitat, Jena, G.D.R.

Google Scholar

[95]

MAC~tTE~, M., AND YOONO, P. 1978. An Introduction to the General Theory of Algorithms. Elsevier North-Holland, New York.

Crossref

Google Scholar

[96]

M~TIN-LOF, P. 1966. The definition of random sequences. Inf. Control 9, 602--619.

Google Scholar

[97]

M~TIN-LOF, P. 1971. Complexity oscillations in infinite binary strings. Z. Wahrscheinlichkeitstheor. Verw. Geb. 19, 225-230.

Google Scholar

[98]

MARYANSKI, F. J., AND BOOTH, T. L. 1977. Inference of finite-state probabilistic grammars. IEEE Trans. Comput. C-26, 521-536.

Google Scholar

[99]

MICHALSKI, R. 1980. Pattern recognition as rule guided inductive inference. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-2, 349-361.

Google Scholar

[100]

MICHALSKi, R., CARBONELL, J., ANO MITCHELL, T., Eds. 1983. Machine Learning. Tioga Publ., Palo Alto, Calif.

Google Scholar

[101]

MICLET, L. 1980. Regular inference with a tail-clustering method. IEEE Tram. Syst. Man Cybern. SMC- 10, 737-743.

Google Scholar

[102]

MINICOZZl, E. 1976. Some natural properties of strong identification in inductive inference. Theor. Comput. ScL 2, 345-360.

Google Scholar

[103]

MITCHELL, T. M. 1982. Generalization as search. Arti{. IntelL 18, 203-226.

Google Scholar

[104]

NIx, R. 1983. Editing by example. Ph.D. dissertation, Computer Science Dept., Yale University, New Haven, Conn.

Google Scholar

[105]

NIX, R. 1984. Editing by example. In Proceedings of the 1 l th A CM Symposium on Principjes of Programming Languages, (Salt Lake City, Utah, Jan. 15-18). ACM, New York, pp. 186-195.

Crossref

Google Scholar

[106]

OSHERSON, D. N., AND WEiNSTEIN, $. 1982. Criteria of language learning. Inf. Control 52, 123-138.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[111]

PLOTKI~, G. D. 1970. A note on inductive generalization, in Machine intelligence 5. Elsevier North- Holland, New York, pp. 153-163.

Google Scholar

[112]

PLOTKIN, G. D. 1971a. Automatic methods ofinductive inference. Ph.D. dissertation, Computer Science Dept., Edinburgh University.

Google Scholar

[113]

PLOTKm, G. D. 1971b. A further note on inductive generalization. In Machine Intelligence 6. Elsevier Notch-Holland, New York, pp. 101-124.

Google Scholar

[114]

PODN}EgS, K. M. 1974. Comparing various concepts of function prediction, Part {. LaW. Gosudar~t. Univ. Uch. Zapiski 210, 68-81 (in Russian).

Google Scholar

[115]

PODNIEKS, K. M. 1975a. Probabilistic synthesis of enumerated classes of functions. Sou. Math. Doki. 16, 1042-1045.

Google Scholar

[116]

POON{EKS, K. M. 19751). Comparing various concepts of function prediction, Part II. LaW. Gosudarst. Univ. Uch. Zapiski 233, 33-44. (in Russian).

Google Scholar

[117]

PUTNAM, H. 1975. Probability and confirmation. In Mathematics, Matter and Method. Cambridge Univ. Press, Cambridge, England.

Google Scholar

[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.

Google Scholar

[119]

SHAPIRO, E. 1981a. Inductive inference of theories from facts. Tech. Rep. 192, Dept. of Computer Science, Yale University, New Haven, Conn.

Google Scholar

[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.

Google Scholar

[121]

SHAPIRO, E. Y. 1982a. Algorithmic program diagnosis, in Proceedings o{ the 9th ACM Symposium on Principles o{ Programming Languages (Albuquerque, N. Mex.). ACM, New York, pp. 299- 308.

Crossref

Google Scholar

[122]

SHAPIRO, E. 1982h. Algorithmic program debugging. Ph.D. dissertation, Computer Science Dept., Yale University, 1982. Published by M.I.T. Press, 1983.

Crossref

Google Scholar

[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.

Google Scholar

[124]

SHINOHARA, T. 1982a. Polynomial time inference of extended regular pattern languages. In Proceedings, So{tware Science and Engineering, Kyoto, Japan.

Crossref

Google Scholar

[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.

Google Scholar

[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.

Google Scholar

[127]

SIMON, H. A., A~O KOTOVSK~, K. 1963. Human acquisition of concepts for sequential patterns. Psych. Rev. 70, 534-546.

Google Scholar

[128]

SMITH, C. H. 1982. The power of pluralism for automatic program synthesis. J. ACM 29, 4 (Oct.), 1144-1165.

Crossref

Google Scholar

[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.

Google Scholar

[130]

SOLOMONOFF, R. J. 1964. A formal theory of inductive inference. In{. Control 7, 1-22, 224-254.

Google Scholar

[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.

Google Scholar

[132]

SOLOMONOFF, R. J. 1978. Complexity.based induction systems: comparisons and convergence theorems. IEEE Trans. in{. Theor. IT-24, 422-432.

Google Scholar

[133]

STOLFO, S. J. 1979. Automatic discovery heuristics for nondeterministic programs from sample execution traces. Ph.D. dissertation, Computer Science Dept., New York University.

Crossref

Google Scholar

[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.

Google Scholar

[135]

SUMMERS, P. D. 1976. Program construction from examples. Ph.D. dissertation, Computer Science Dept., Yale University, New Haven, Conn.

Crossref

Google Scholar

[136]

SUMMERS, P. D. 1977. A methodology for LISP program construction from examples. J. A CM 24, 1 (Jan.), 161-175.

Crossref

Google Scholar

[137]

THIELE, H. 1973. Lernverfahren zur Erkennung formaler Sprachen. Kyberr~ Forsch. 3, 11-93.

Google Scholar

[138]

TH{ELP., H. 1975. Zur Charakterisierung yon grkennungssytemen mit einbettendem Konvergenzbegriff. Kornpliziertheit Lern Erkennungsprozessen 2. 188--207. Jena, G.D.R.

Google Scholar

[139]

VAN DER MUDE, A., AND WALKER, A. 1978. On the inference of stochastic regular grammars. Inf. Control 38, 310-329.

Google Scholar

[140]

VEELENTURF, L. P. J. 1978. Inference of sequential machines from sample computations. IEEE Trans. Comput. C-27, 167-170.

Google Scholar

[141]

VERE, S. A. 1980. Multilevel counterfactuals for generalizations of relational concepts and productions. Artif {ntell~ I4, 139-164.

Google Scholar

[142]

VERE, S. A. 1981. Constrained N-to-1 generalization. Preprint, Jet Propulsion Laboratory, Pasadena, Calif.

Google Scholar

[143]

WATANA~E, S. 1960. Information-theoreticalaspects of inductive and deductive inference. IBM J. Res. Devel. 4, 208-231.

Google Scholar

[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.

Google Scholar

[145]

WEXLER, K., AND CULtCOVER, P. 1980. Formal Principles of Language Acquisition. M.I.T. Press, Cambridge, Mass.

Google Scholar

[146]

WHARTON, R. M. 1974. Approximate language identification. Inf. Control 26, 236-255.

Google Scholar

[147]

WHARTOn, R. M. 1977. Grammar enumeration and inference. Inf. Control 33, 253-272.

Google Scholar

[148]

WIEHAGEN, R. 1976. Limes-erkennung rekursiver Funktionen durch spezielle Stratigen. Elektron. lnforma~ionsverarbeit. Kybern. (ELK) 12, 93-99.

Google Scholar

[149]

W{~.HAGEN, R. 1977. Identification of formal languages. In Lecture Notes in Computer Science, vol. 53. Springer-Verlag, New York, pp. 571-579.

Google Scholar

[150]

WIEHAGEN, R. 1978. Characterization problems in the theory of inductive inference. In Proceedings of the 5th Colloquium on Automata, Languages, and Programming (Udine, Italy, July), Lecture Notes on Computer Science, vol. 62. Springer- Verlag, New York, pp. 494-508.

Crossref

Google Scholar

[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.

Google Scholar

[152]

WINSTON, P. 1975. Learning Structural Descriptions from Examples. McGraw-Hill, New York.

Google Scholar

[153]

ZLOOF, M. 1977. Query-by-Example: A data base language. IBM Syst. J. 16, 324-343.

Google Scholar

[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.

Google Scholar

Cited By

View all

Pickering ESapsis T(2024)Information FOMO: The Unhealthy Fear of Missing Out on Information—A Method for Removing Misleading Data for Healthier ModelsEntropy10.3390/e2610083526:10(835)Online publication date: 30-Sep-2024
https://doi.org/10.3390/e26100835
Ribeiro TVeloso ABrinson P(2024)Exploring the Variables of Empathy in Gamers: A Comprehensive SurveyHCI in Games10.1007/978-3-031-60692-2_8(98-113)Online publication date: 29-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-60692-2_8
Shi QXu XZhang XCalandrino JTroncoso C(2023)Extracting protocol format as state machine via controlled static loop analysisProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620630(7019-7036)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620630
Show More Cited By

Recommendations

From inductive inference to algorithmic learning theory
Abstract
We present two phenomena which were discovered in pure recursion-theoretic inductive inference, namely inconsistent learning (learing strategies producing apparently “senseless” hypotheses can solve problems unsolvable by “reasonable” learning ...
Quantum inductive inference by finite automata

Freivalds and Smith [R. Freivalds, C.H. Smith Memory limited inductive inference machines, Springer Lecture Notes in Computer Science 621 (1992) 19-29] proved that probabilistic limited memory inductive inference machines can learn with probability 1 ...
Inductive inference of approximations for recursive concepts
Algorithmic learning theory (ALT 2000)

This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i.e., learning with anomalies. ...

Comments

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 15, Issue 3

Sept. 1983

114 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/356914

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1983

Published in CSUR Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

685
Total Citations
View Citations
4,875
Total Downloads

Downloads (Last 12 months)427
Downloads (Last 6 weeks)29

Reflects downloads up to 22 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pickering ESapsis T(2024)Information FOMO: The Unhealthy Fear of Missing Out on Information—A Method for Removing Misleading Data for Healthier ModelsEntropy10.3390/e2610083526:10(835)Online publication date: 30-Sep-2024
https://doi.org/10.3390/e26100835
Ribeiro TVeloso ABrinson P(2024)Exploring the Variables of Empathy in Gamers: A Comprehensive SurveyHCI in Games10.1007/978-3-031-60692-2_8(98-113)Online publication date: 29-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-60692-2_8
Shi QXu XZhang XCalandrino JTroncoso C(2023)Extracting protocol format as state machine via controlled static loop analysisProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620630(7019-7036)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620630
Chesani FFrancescomarino CGhidini CLoreti DMaggi FMello PMontali MTessaris S(2023)Process Discovery on Deviant Traces and Other Stranger ThingsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.323220735:11(11784-11800)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3232207
BELOT G(2023)UNPRINCIPLEDThe Review of Symbolic Logic10.1017/S1755020323000151(1-40)Online publication date: 13-Jun-2023
https://doi.org/10.1017/S1755020323000151
Icarte RKlassen TValenzano RCastro MWaldie EMcIlraith S(2023)Learning Reward Machines: A Study in Partially Observable Reinforcement LearningArtificial Intelligence10.1016/j.artint.2023.103989(103989)Online publication date: Aug-2023
https://doi.org/10.1016/j.artint.2023.103989
Pitts J(2023)Does Meta-induction Justify Induction: Or Maybe Something Else?Journal for General Philosophy of Science10.1007/s10838-022-09620-754:3(393-419)Online publication date: 22-Feb-2023
https://doi.org/10.1007/s10838-022-09620-7
Mohammadi FEggenweiler EFlemisch BOladyshkin SRybak ISchneider MWeishaupt K(2023)A surrogate-assisted uncertainty-aware Bayesian validation framework and its application to coupling free flow and porous-medium flowComputational Geosciences10.1007/s10596-023-10228-z27:4(663-686)Online publication date: 13-Jul-2023
https://doi.org/10.1007/s10596-023-10228-z
Arnold OJantke K(2023)Verständliche Künstliche Intelligenz in Assistenzsystemen an Mensch-System-SchnittstellenEntrepreneurship der Zukunft10.1007/978-3-658-42060-4_13(317-343)Online publication date: 30-Dec-2023
https://doi.org/10.1007/978-3-658-42060-4_13
Chu WChen SBonsangue MShi Z(2023)Approximately Learning Quantum AutomataTheoretical Aspects of Software Engineering10.1007/978-3-031-35257-7_16(268-285)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35257-7_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Recommendations

From inductive inference to algorithmic learning theory

Quantum inductive inference by finite automata

Inductive inference of approximations for recursive concepts

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations