acl acl2010 acl2010-103 acl2010-103-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jeffrey Heinz ; James Rogers
Abstract: Strictly Piecewise (SP) languages are a subclass of regular languages which encode certain kinds of long-distance dependencies that are found in natural languages. Like the classes in the Chomsky and Subregular hierarchies, there are many independently converging characterizations of the SP class (Rogers et al., to appear). Here we define SP distributions and show that they can be efficiently estimated from positive data.
R.B. Applegate. 1972. Inese˜ no Chumash Grammar. Ph.D. thesis, University of California, Berkeley. R.B. Applegate. 2007. Samala-English dictionary : a guide to the Samala language of the Inese˜ no Chumash People. Santa Ynez Band of Chumash Indians. Eric Bakovi´ c. 2000. Harmony, Dominance and Control. Ph.D. thesis, Rutgers University. D. Beauquier and Jean-Eric Pin. 1991 . Languages and scanners. Theoretical Computer Science, 84:3–21 . Eric Brill. 1995. Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging. ComputationalLinguistics, 21(4):543–566. J. A. Brzozowski and Imre Simon. 1973. Characterizations of locally testable events. Discrete Mathe- matics, 4:243–271. Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on Information Theory. IT-2. J. S. Coleman and J. Pierrehumbert. 1997. Stochastic phonological grammars and acceptability. In Computational Phonology, pages 49–56. Somerset, NJ: Association for Computational Linguistics. Third Meeting of the ACL Special Interest Group in Computational Phonology. Colin de la Higuera. in press. Grammatical Inference: Learning Automata and Grammars. Cambridge University Press. Pedro Garc ı´a and Jos e´ Ruiz. 1990. Inference of ktestable languages in the strict sense and applications to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9:920–925. Pedro Garc ı´a and Jos e´ Ruiz. 1996. Learning kpiecewise testable languages from positive data. In Laurent Miclet and Colin de la Higuera, editors, Grammatical Interference: Learning Syntax from Sentences, volume 1147 of Lecture Notes in Computer Science, pages 203–210. Springer. Pedro Garcia, Enrique Vidal, and Jos e´ Oncina. 1990. Learning locally testable languages in the strict sense. In Proceedings of the Workshop on Algorithmic Learning Theory, pages 325–338. Gunnar Hansson. 2001. Theoretical and typological issues in consonant harmony. Ph.D. thesis, University of California, Berkeley. Bruce Hayes and Colin Wilson. 2008. A maximum entropy model of phonotactics and phonotactic learning. Linguistic Inquiry, 39:379–440. Jeffrey Heinz. 2007. The Inductive Learning of Phonotactic Patterns. Ph.D. thesis, University of California, Los Angeles. Jeffrey Heinz. to appear. Learning long distance phonotactics. Linguistic Inquiry. John Hopcroft, Rajeev Motwani, and Jeffrey Ullman. 2001. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. Frederick Jelenik. 1997. Statistical Methods for Speech Recognition. MIT Press. C. Douglas Johnson. 1972. Formal Aspects of Phonological Description. The Hague: Mouton. A. K. Joshi. 1985. Tree-adjoining grammars: How much context sensitivity is required to provide reasonable structural descriptions? In D. Dowty, L. Karttunen, and A. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge University Press. Daniel Jurafsky and James Martin. 2008. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. Prentice-Hall, 2nd edition. Ronald Kaplan and Martin Kay. 1994. Regular models of phonological rule systems. Computational Linguistics, 20(3):331–378. Gregory Kobele. 2006. Generating Copies: An Investigation into Structural Identity in Language and Grammar. Ph.D. thesis, University of California, Los Angeles. Leonid (Aryeh) Kontorovich, Corinna Cortes, and Mehryar Mohri. 2008. Kernel methods for learning languages. Theoretical Computer Science, 405(3):223 236. Algorithmic Learning Theory. – M. Lothaire, editor. 1997. Combinatorics on Words. Cambridge University Press, Cambridge, UK, New York. A. A. Markov. 1913. An example of statistical study on the text of ‘eugene onegin’ illustrating the linking of events to a chain. Robert McNaughton and Simon Papert. Counter-Free Automata. MIT Press. 197 1. A. Newell, S. Langer, and M. Hickey. 1998. The r oˆle ofnatural language processing in alternative and augmentative communication. Natural Language Engineering, 4(1): 1–16. Dominique Perrin and Jean-Eric Pin. 1986. FirstOrder logic and Star-Free sets. Journal of Computer and System Sciences, 32:393–406. Catherine Ringen. 1988. Vowel Harmony: Theoretical Implications. Garland Publishing, Inc. 895 James Rogers and Geoffrey Pullum. to appear. Aural pattern recognition experiments and the subregular hierarchy. Journal of Logic, Language and Information. James Rogers, Jeffrey Heinz, Matt Edlefsen, Dylan Leeman, Nathan Myers, Nathaniel Smith, Molly Visscher, and David Wellcome. to appear. On languages piecewise testable in the strict sense. In Proceedings of the 11th Meeting of the Assocation for Mathematics of Language. Sharon Rose and Rachel Walker. 2004. A typology of consonant agreement as correspondence. Language, 80(3):475–531. Jacques Sakarovitch and Imre Simon. 1983. Subwords. In M. Lothaire, editor, Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and Its Applications, chapter 6, pages 105–134. Addison-Wesley, Reading, Massachusetts. Stuart Shieber. 1985. Evidence against the contextfreeness of natural language. Linguistics and Philosophy, 8:333–343. Imre Simon. 1975. Piecewise testable events. In Automata Theory and Formal Languages: 2nd Grammatical Inference conference, pages 214–222, Berlin ; New York. Springer-Verlag. Howard Straubing. 1994. Finite Automata, Formal Logic and Circuit Complexity. Birkh ¨auser. Wolfgang Thomas. 1982. Classifying regular events in symbolic logic. Journal of Computer and Systems Sciences, 25:360–376. Enrique Vidal, Franck Thollard, Colin de la Higuera, Francisco Casacuberta, and Rafael C. Carrasco. 2005a. Probabilistic finite-state machines-part I. IEEE Transactions on Pattern Analysis andMachine Intelligence, 27(7): 1013–1025. Enrique Vidal, Frank Thollard, Colin de la Higuera, Francisco Casacuberta, and Rafael C. Carrasco. 2005b. Probabilistic finite-state machines-part II. IEEE Transactions on Pattern Analysis andMachine Intelligence, 27(7): 1026–1039. 896