Papers

• Jeffery Heinz and Jim Rogers: Learning Subregular Classes of Languages with Factored Deterministic Automata with Jeff Heinz, U. Delaware. 13th Meeting of the Association for Mathematics of Language. pdf (90KB).
• Cognitive and Sub-Regular Complexity with Jeff Heinz, U. Delaware, M. Ferro, J. Hurst, D. Lambert and S. Wibel, EC. 17th Conference on Formal Grammars, Opole, Poland, Aug. 2012. pdf (200KB).
• Estimating Strictly Piecewise Distributions with Jeff Heinz, U. Delaware. 48th Meeting of the Association for Computational Linguistics, Uppsala, Sweden, 2010. pdf (136KB).
• On Languages Piecewise Testable in the Strict Sense, with Jeff Heinz (U. Delaware) and a host of Earlham undergrads. Eleventh Meeting on Mathematics of Language, Bielefeld, Germany, 2009. (pdf)
• The Use of Formal Language Theory in Studies of Artificial Language Learning: a proposal for distinguishing the differences between human and nonhuman animal learners with Marc D. Hauser, Harvard. In Recursion and Human Language, Ed. by Hulst, Harry van der. de Gruyter, 2010, Studies in Generative Grammar [SGG] 104. (pdf)
• Aural Pattern Recognition Experiments and the Subregular Hierarchy, with Geoff Pullum (U. Edinburgh). Journal of Logic, Language and Information, 20:329–342, 2011. (pdf). Presented at Tenth Meeting on Mathematics of Language (UCLA), 2007. (pdf)
• The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars, with Stephan Kepser (U. Tuebingen). Tenth Meeting on Mathematics of Language (UCLA), 2007. (pdf)
• On Scrambling, Another Perspective (gzipped postscript, 65K) (pdf, 113K)
  Seventh Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+7), Vancouver, 2004.
• Wrapping of Trees. (gzipped postscript, 48K) (pdf, 89K)
  48th Annual Meeting of the Association for Computational Linguistics, Barcelona, 2004.
• wMSO Theories as Grammar Formalisms (gzipped postscript, 140K) (pdf, 378K)
  Theoretical Computer Science, v 293, n 2, pp 291-320, 2003.
• One More Perspective on Semantic Relations in TAG (gzipped postscript, 72K) (pdf, 46K)
  Presented at the Sixth International Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+6), Venice, 2002.
• Syntactic Structures as Multi-Dimensional Trees. (gzipped postscript, 180K) (pdf, 740K) (abstract) This surveys the work below along with some more recent work. A preliminary version was presented at the ESSLLI'00 workshop on trees. This version appears in Research on Language and Computation, v 1, n 3-4, pp 265-305, 2003.
• Generalized Tree-Adjoining Grammar. (gzipped postscript, 131K) (pdf, 268K) (abstract) A paper presented at the Sixth Meeting on Mathematics of Language, 1999.
• A Descriptive Characterization of Tree-Adjoining Languages (Full Version) (gzipped postscript, 78K) (abstract) This is the full version of a paper in the proceedings of COLING-ACL'98 as a project note.
• On Defining TALs with Logical Constraints (gzipped postscript 65K) Paper presented at the Fourth International Workshop on Tree Adjoining Grammars and Related Frameworks (TAG+4), Phila. Aug. 1999.
• Thomas Cornell and ---. Model Theoretic Syntax (gzipped postscript 79K) In The Glot International State of the Article Book I Holland Academic Graphics.
• The Descriptive Complexity of Generalized Local Sets (gzipped postscript 111K): A paper on the class of sets of trees definable in $L^2_{K,P}$ if we do not include an explicit finite bound on the branching. In Mathematics of Syntactic Structure. Mouton/deGruyter. Collected papers from the workshop of the same name at ESSLLI'96, Prague.
• A Unified Notion of Derived and Derivation Structures in TAG (Preliminary version.) (gzipped postscript, 52K) : This is an extended abstract which appears in the MOL 5 proceedings.
• Strict LT_2 : Regular :: Local : Recognizable (gzipped postscript 104K): A paper on the descriptive complexity of local sets and on parallels between language-theoretic complexity classes in the domain of strings and those in the domain of trees which was presented at the Logical Aspects of Computational Linguistics conference, Villers-l\`es-Nancy, Sept. 1996.
• A Model-Theoretic Framework for Theories of Syntax (gzipped postscript, 47K) (abstract): A preprint of a paper which appears in Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics.
• ``Grammarless'' Phrase Structure Grammar (gzipped postscript, 112K) (abstract) A preprint of an article that appears in Linguistics and Philosophy, v20:721--746. (Following TR is related.)
• What Does a Grammar Formalism Say About a Language? (gzipped postscript 96K) (abstract): A draft of a TR in which a model-theoretic reinterpretation of GPSG is used as the basis of an exploration of some issues in linguistic metatheory.
• A First-Order Axiomatization of the Theory of Finite Trees (compressed postscript, 150K) (abstract): A preprint of an article, co-authored by Rolf Backofen and K. Vijay-Shanker, which appears in Vol 4 (pp 5--39) of the Journal of Logic, Language, and Information.
• On Descriptive Complexity, Language Complexity,and GB (compressed postscript, 130K) (abstract): A preprint of an article which appears in Specifying Syntactic Structures, papers from the Logic, Structures, and Syntax workshop, Amsterdam, Sept. 1994). This is a brief sketch of the topics covered in A Descriptive Approach to Language-Theoretic Complexity.
• Obtaining Trees from Their Descriptions: An Application to Tree-Adjoining Grammars (gzipped postscript 109K) (abstract): A preprint of an article which appears in Vol 10 (pp 401--421) of Computational Intelligence.
• Capturing CFLs with Tree Adjoining Grammars (gzipped postscript 54K) (abstract): A preprint of a paper which appears in Proceedings of the 32nd Annual Meeting of the Association for Computational Linguistics.
• More to come ...