Theory Group

The Theory Group is a student faculty research group which includes students of all levels working together with a faculty advisor, Jim Rogers. Our broad focus is on problems in the area of formal language theory (such as is introduced in CS-380 Theory of Computation, although you don't necessarily need to have taken CS-380 to participate). Our specific focus is on computational approaches to studying natural languages.

Our current project is studying the formal complexity of stress patterns that occur in the words of human languages with the goal of gaining insight into the abstract nature of the mechanisms which humans use to recognize them when listening, to generate them when speaking and to learn them.

Previous projects involved developing parsing algorithms for Multi-Dimensional Grammars and Automata, generalizations of Context-Free Grammars which have additional descriptive power sufficient to capture many of the constructions occurring in natural languages that cannot be described by CFGs.

More detailed descriptions of our current projects are available either on the projects pages by following the specific links in the navigation menu.

People

Currently there are three students and one faculty advisor working in the theory group.

• David Wellcome A first year, as yet non-aligned.
• Nate Smith A second year CS major.
• Dylan Leeman A senior CS major.
• Nathan Myers A senior CS major.
• Jim Rogers The faculty advisor.

Past Participants

• David Brown 2006.
• Colin Kern 2006.
• Alex Lemann 2006.
• Tom Weiss-Lehman 2006.
• Greg Sandstrom 2005.
• Ian Kelly 2004.

Collaborative Alumni/Student/Faculty Research

During the summer of 2004 we pursued our research under the auspices of the Ford-Knight program, the Matthews Summer Research Fund and the CS Department's Collaborative Research Fund. We actively solicited participation of Earlham CS alumni in this effort. The student participants included David Brown, Ian Kelly, Colin Kern and Alex Lemann. Our specific goals for the summer were to develop CKY-style parsing algorithms for at least the three-dimensional grammars and automata with good expectations of extending these to the arbitrary dimension cases. We succeeded in developing inference rules for the three-dimensional case, and from there developed an algorithm.

There are a variety of projects that these goals entail, from foundational issues in the abstract structure of the algorithms, through implementation issues in coding these algorithms flexibly and efficiently, through support applications such as graphical input and output of multidimensional structures. We have a certain amount of existing infrastructure for most of these projects. If you would like to participate, please contact

Papers

Background papers

Computational Phonology

• Jeffrey Heinz. Inductive Learning of Phonotactic Patterns Jeff Heinz's dissertation.
• Jim Rogers and Geoff Pullum. Aural Pattern Recognition Experiments and the Subregular Hierarchy Tenth Meeting on Mathematics of Language
• Jim Rogers and Geoff Pullum. Animal Pattern-Learning Experiments: Some Mathematical Background A samizdat paper from Fall 2005.

Multi-Dimensional Tree Grammars

• wMSO Theories as Grammar Formalisms. (gzipped postscript, 140K) (pdf, 378K)
  Jim Rogers. Theoretical Computer Science, v 293, n 2, pp 291-320, 2003.
• Syntactic Structures as Multi-Dimensional Trees. (gzipped postscript, 180K) (pdf, 740K) (abstract)
  Jim Rogers. Research on Language and Computation, v 1, n 3-4, pp 265-305, 2003.
• On Scrambling, Another Perspective. (gzipped postscript, 65K) (pdf, 113K)
  Jim Rogers. Presented at the Seventh Workshop on Tree-Adjoining Grammars and Related Formalisms (TAG+7), Vancouver, 2004.
• Wrapping of Trees. (gzipped postscript, 48K) (pdf, 89K)
  Jim Rogers. 42nd Annual Meeting of the Association for Computational Linguistics, pp. 558--565, Barcelona, 2004.
• Automata Theory for XML Researchers. (gzipped postscript, 166K) (pdf, 128K)
  Frank Nevin. ACM SIGMOD Record, v 31, n 3, pp 39-46, 2002.

Other papers we have worked with

• Deductive Parsing (gzipped postscript, 160k) (pdf, 505k)
• Towards a Uniform Formal Framework for Parsing (gzipped postscript, 76k) (pdf, 312k)

Drafts of our work

• Representing Multidimensional Trees (long version) (gzipped postscript, 210k) (pdf, 247k)
• Representing Multidimensional Trees (short version) (gzipped postscript, 147k) (pdf, 150k) Submitted to MCURCSM '04.
• A CNF Transformation for Multidimensional Trees (gzipped postscript, 118k) (pdf, 113k) Submitted to MCURCSM '04.

| CS Home | Earlham College | WebDB | Earlham Mail | Earlham Libraries | Word Online |

Copyright © 1996-2002 by Earlham College Computer Science Department.
If you're curious about why we copyright, see Peter Suber's Why Copyright Web Documents?.

Looking for something that's not here? Contact:
Last updated: Friday, 09-Nov-2007 09:56:00 EST
#5497