L. F. Fass
Abstract
Inductive inference is a learning process based on discovering models for bodies of knowledge, given sample information. The inference process we discuss here is concerned with inductive acquisition of syntactic models for context-free languages (CFLs), given appropriate language samples. The knowledge to be modeled in this case is any CFL L, with the model to be determined a recognitive or generative characterization of L's syntactic structure. L will be learned syntactically once a machine M recognizing L, or a context-free grammar (CFG) G generating L, is inductively inferred from a sentence sample. The capability of distinguishing between L and its complement, or of generating all and only L's sentences, is the knowledge acquired, with the learner (inference process) gaining this knowledge by acquiring M or G. An observer (informant, teacher, or oracle) has such knowledge of L and can provide the learner with appropriate sample information to ensure that M or G is correctly identified.
- Angluin, D. and C.H. Smith, "Inductive Inference: Theory and Methods," Computing Surveys, Vol. 15, No. 3 (September, 1983), pp. 237-269. Google Scholar
Digital Library
- Bainbridge, E.S., and L.F. Fass, "Minimal Structures for Context-Free Languages," (project in progress).Google Scholar
- Berwick, R.C., and S.F. Pilato, "Reversible Automata and Induction of the English Auxiliary System," IJCAI 85, Vol. 2, pp. 880-882. Google ScholarDigital Library
- Fass, L.F., "On the Inference of Canonical Context-Free Grammars," SIGACT News, Vol. 17, No. 4 (Spring, 1986), pp. 55-60. Google ScholarDigital Library
- Fass, L.F., "A minimal Deterministic Acceptor for any (Structured) Context-Free Language," in preparation.Google Scholar
- Fass, L.F. and W.I. Gasarch, "Complexity Issues in Skeletal Automata," Computer Science Technical Report Series, TR-2035, University of Maryland, College Parks, 1988.Google Scholar
- Hoproft, J.E. and J.D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. Google ScholarDigital Library
- Levy, L.S. and A.K. Joshi, "Skeletal Structural Descriptions," Information and Control, Vol. 39 (1978), PP. 192-211.Google ScholarCross Ref
- Lust, B. "Remarks on the Psychological Reality of the Subset Principle: Its Relation to Universal Grammar as a Model of the Initial State," Proc. of the Univ. of Massachusetts Cognitive Science Conference, August, 1986.Google Scholar
- McNaughton, R., "Parenthesis Grammars," JACM, Vol. 134, (1967) pp. 490-500. Google ScholarDigital Library
- Myhill, J. "Finite Automata and the Representation of Events," WADC Tech. Rpt., pp. 57-624, Wright-Patterson AFB, 1957.Google Scholar
- Nerode, A., "Linear Automaton Transformations," Proc. AMS, IX (1959), pp. 541-544.Google Scholar
- Paul, M.C. and S.H. Unger, "Structural Equivalence of Context-Free Languages," JCSS, Vol. 2 (1968), pp. 427-463.Google Scholar
- Thatcher, J.W., "Characterizing Derivation Trees of Context-Free Languages through a Generalization of Finite Automata Theory," JCSS, (1967) pp. 317-322.Google Scholar
- Thatcher, J.W. and J.B. Wright, "Generalized Finite Automata Theory with an Application to a Decision Problem of Second Order Logic," Mathematical Systems Theory, Vol. 2 (1970), pp. 57-81.Google ScholarCross Ref
Index Terms
- Learnability of CFLs: inferring syntactic models from constituent structure
Recommendations
Incremental syntactic language models for phrase-based translation
HLT '11: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1This paper describes a novel technique for incorporating syntactic knowledge into phrase-based machine translation through incremental syntactic parsing. Bottom-up and top-down parsers typically require a completed string as input. This requirement ...
Constituent reordering and syntax models for English-to-Japanese statistical machine translation
COLING '10: Proceedings of the 23rd International Conference on Computational LinguisticsWe present a constituent parsing-based reordering technique that improves the performance of the state-of-the-art English-to-Japanese phrase translation system that includes distortion models by 4.76 BLEU points. The phrase translation model with ...
CCG syntactic reordering models for phrase-based machine translation
WMT '12: Proceedings of the Seventh Workshop on Statistical Machine TranslationStatistical phrase-based machine translation requires no linguistic information beyond word-aligned parallel corpora (Zens et al., 2002; Koehn et al., 2003). Unfortunately, this linguistic agnosticism often produces ungrammatical translations. Syntax, ...
Comments