Browse by Topic

More Output

  1. A Subregular Bound on the Complexity of Lexical Quantifiers

    Graf, Thomas

    Abstract Semantic automata theory studies the complexity of generalized quantifiers in terms of the string languages that describe their truth conditions. An important point has gone unnoticed so far: for most quantifiers that are determiners, these string languages are subregular. Whereas quantifier phrases …

    read more
  2. C-Command Dependencies as TSL String Constraints

    Graf, Thomas, and Nazila Shafiei

    Abstract We provide a general formal framework for analyzing c-command based dependencies in syntax, e.g. binding and NPI licensing, from a subregular perspective. C-command relations are represented as strings computed from Minimalist derivation trees, and syntactic dependencies are shown …

    read more
  3. Case Assignment in TSL Syntax: A Case Study

    Vu, Mai Ha, Nazila Shafiei, and Thomas Graf

    Abstract Recent work suggests that the subregular complexity of syntax might be comparable to that of phonology and morphology. More specifically, whereas phonological and morphological dependencies are tier-based strictly local over strings, syntactic dependencies are tier-based strictly …

    read more
  4. Sensing Tree Automata as a Model of Syntactic Dependencies

    Graf, Thomas, and Aniello De Santo

    Files

    @misc{GrafDeSanto19MOLtalk,
        title = {Sensing Tree Automata as a Model of Syntactic Dependencies},
        author = {Graf, Thomas and De Santo, Aniello},
        year = {2019},
        note = {Slides of a talk given at the 16th meeting on the mathematics of language ({MOL} 2019 …
    read more
  5. The Surprising Simplicity of Syntax: Derivation Trees, Subregular Complexity, and What It Implies for Language and Cognition

    Graf, Thomas

    Abstract It is a well-known fact of computational linguistics that syntax is mildly context-sensitive and thus highly complex —- certainly more complex than phonology or morphology. This complexity is at odds with the ease of language acquisition and the impressive speed of human sentence …

    read more
  6. Adjunction to Movement Paths: Floating Quantifiers as the Little Brother of Parasitic Gaps

    Graf, Thomas

    Abstract A lot of recent work in computational phonology seeks to pinpoint the complexity of phonotactic dependencies from a formal perspective. Numerous mathematical classes have been proposed, but Graf (2017) subsumes them all under the umbrella of interval-based strictly piecewise dependencies (IBSP). IBSP …

    read more
  7. Tiers and Relativized Locality Across Language Modules

    Graf, Thomas, Alëna Aksënova, Hyunah Baek, Aniello De Santo, Hossep Dolatian, Sedigheh Moradi, Jon Rawski, Suji Yang, and Jeffrey Heinz

    Abstract Heinz and Idsardi (2013) draw attention to a profound computational difference between syntax and phonology: phonology only requires regular computations over strings (Johnson 1972 …

    read more
  8. Grammar Size and Quantitative Restrictions on Movement

    Graf, Thomas

    Abstract This work is a first tentative step towards motivating constraints on movement as a mechanism for minimizing grammar size.

    Recently is has been proved that every Minimalist grammar can be converted into a strongly equivalent single movement normal form such that every …

    read more
  9. One Reason to Move, a Million Reasons to Be an Island: Third-Factor Explanations from Computational Syntax

    Graf, Thomas

    Abstract Two linguistic findings are commonly taken for granted yet are anything but trivial:

    1. Phrases can be displaced from their base position.
    2. Some phrases block displacement.

    On a technical level, these properties are hashed out in terms of movement and islands. From a …

    read more
  10. Graph Transductions and Typological Gaps in Morphological Paradigms

    Graf, Thomas

    Abstract Several typological gaps have attracted a lot of interest in the linguistic literature recently. These concern the Person Case Constraint and the absence of ABA patterns in adjectival gradation, pronoun suppletion, case syncretism, and singular noun allomorphy, among others. This paper is …

    read more
  11. Do We Need Features for Morphosyntax?

    Graf, Thomas

    Abstract Bobaljik & Sauerland’s *ABA and the Combinatorics of Morphological Features attempts to explain the absence of ABA patterns across languages in terms of feature combinatorics. Their approach marks a step in the right direction by focusing on the algebra underlying the feature …

    read more
  12. It’s a (Sub-)Regular Conspiracy: Locality and Computation in Phonology, Morphology, Syntax, and Semantics

    Graf, Thomas

    Abstract It is commonly believed that phonology, morphology, syntax, and semantics are distinct modules of language, governed by very different principles with little common ground. Nonetheless several approaches (e.g. Government Phonology, Distributed Morphology) subscribe to the idea that at least some of …

    read more
  13. Computational Parallels Across Language Modules

    Graf, Thomas

    Abstract Linguists study a variety of aspects of language, including phonology, morphology, and syntax. It is commonly believed that those are distinct modules of language, governed by very different principles and consequently studied with very different tools. While there have been attempts at …

    read more
  14. Morphotactics as Tier-Based Strictly Local Dependencies

    Aksënova, Alëna, Thomas Graf, and Sedigheh Moradi

    Abstract It is commonly accepted that morphological dependencies are finite-state in nature. We argue that the upper bound on morphological expressivity is much lower. Drawing on technical results from computational phonology, we show that a variety of morphotactic …

    read more
  15. An Alternate View on Strong Lexicalization in TAG

    De Santo, Aniello, Alëna Aksënova, and Thomas Graf

    Abstract TAGs were recently shown not to be closed under strong lexicalization but to be strongly lexicalizable by context-free tree grammars of rank 2. This paper presents an alternative lexicalization procedure that builds on an earlier generalization …

    read more
  16. Memory Usage Predicts Relative Difficulty in Human Sentence Processing

    Graf, Thomas, James Monette, Robert Pasternak, and Chong Zhang

    Files [pdf] [code]

    @Misc{GrafEtAl16IACSposter,
      author    = {Graf, Thomas and Monette, James and Pasternak, Robert and Zhang, Chong},
      title     = {Memory Usage Predicts Relative Difficulty in Human Sentence Processing},
      year      = {2016},
      note      = {Poster presented at the {IACS} {R …
    read more
  17. Tier-Based Strict Locality in Phonology and Morphology

    Aksënova, Alëna, Thomas Graf, and Sedigheh Moradi

    Files

    @misc{AksenovaEtAl16NECPhontalk,
      author = {Aks\"{e}nova, Al\"{e}na and Graf, Thomas and Moradi, Sedigheh},
      title = {Tier-Based Strict Locality in Phonology and Morphology},
      year = {2016},
      note = {Slides of a talk given at the 10th Northeast Computational Phonology …
    read more
  18. Adjuncts, Conjuncts, Ojuncts: Deriving Strong Island Constraints

    Graf, Thomas

    Abstract Adjuncts differ from arguments by a number of properties, in particular i) optionality and ii) their island status, which renders them opaque for extraction of subconstituents. Conjuncts, too, are optional and forbid extraction. Starting from this basic observation, I demonstrate that islandhood …

    read more
  19. A Refined Notion of Memory Usage for Minimalist Parsing

    Graf, Thomas, Brigitta Fodor, James Monette, Gianpaul Rachiele, Aunika Warren, and Chong Zhang

    Abstract Recently there has been a lot of interest in testing the processing predictions of a specific top-down parser for Minimalist grammars (Stabler 2012). Most of this work relies on memory-based difficulty …

    read more
  20. A Hidden Consensus: Computational Invariants of Minimalist Syntax

    Graf, Thomas

    Abstract A common sentiment among linguists is that the Minimalist literature features a dazzling array of competing proposals that seem to share little common ground in their technical assumptions. While differences certainly do exist between accounts, a computationally informed perspective reveals a set …

    read more
  21. Commonality in Disparity: The Computational View of Syntax and Phonology

    Graf, Thomas, and Jeffrey Heinz

    Abstract Heinz and Idsardi (2013) draw attention to a computational difference between syntax and phonology established by earlier research: phonology only requires regular computations over strings (Johnson 1972, Kaplan and Kay 1995), whereas syntax involves non-regular computations over strings (Chomsky …

    read more
  22. A Computational Guide to the Dichotomy of Features and Constraints

    Graf, Thomas

    Abstract I draw on various result from mathematical linguistics to argue that feature-based accounts and constraint-based ones should not be viewed as competing with each other but rather as complementing each other. In particular, recent results on Minimalist grammars show that features and …

    read more
  23. Models of Adjunction in Minimalist Grammars

    Graf, Thomas

    Abstract Three closely related proposals for adding (cyclic) adjunction to Minimalist grammars are given model-theoretic definitions and investigated with respect to their linguistic and formal properties. While they differ with respect to their linguistic adequacy, they behave largely the same on a computational …

    read more
  24. Feature Geometry and the Person Case Constraint: An Algebraic Link

    Graf, Thomas

    Abstract The Person Case Constraint blocks certain combinations of clitics and weak pronouns in a variety of languages. Out of the numerous logical possibilities, only four variants of the Person Case Constraint are attested. I show that these four variants form a natural …

    read more
  25. The Syntactic Algebra of Adjuncts

    Graf, Thomas

    Abstract I argue that the special behavior of adjuncts is a consequence of two properties that set them apart from arguments: optionality and independence.

    • Optionality Adjuncts can be omitted.
    • Independence Independently well-formed adjuncts can be combined.

    These properties yield several grammaticality inferences that …

    read more
  26. Of Tops and Bottoms: The Algebra of Person Case Constraints

    Graf, Thomas

    Abstract The Person Case Constraint blocks certain combinations of clitics and weak pronouns in a variety of languages. Out of the numerous logical possibilities, only four variants of the Person Case Constraint are attested. I show that these four variants form a natural …

    read more
  27. Movement-Generalized Minimalist Grammars

    Graf, Thomas

    Abstract A general framework is presented that allows for Minimalist grammars to use arbitrary movement operations under the proviso that they are all definable by monadic second-order formulas over derivation trees. Lowering, sidewards movement, and clustering, among others, are the result of instantiating …

    read more
  28. Locality and the Complexity of Minimalist Derivation Tree Languages

    Graf, Thomas

    Abstract Minimalist grammars provide a formalization of Minimalist syntax which allows us to study how the components of said theory affect its expressivity. A central concern of Minimalist syntax is the locality of the displacement operation Move. In Minimalist grammars, however, Move is …

    read more
  29. Closure Properties of Minimalist Derivation Tree Languages

    Graf, Thomas

    Abstract Recently, the question has been raised whether the derivation tree languages of Minimalist grammars (MGs; Stabler 1997, Stabler & Keenan 2003) are closed under intersection with regular tree languages (Graf 2010). Using a variation of a proof technique devised by Thatcher (1967), I …

    read more
  30. Optimality Is Not a Race: Against a Performance-Based View of Reference-Set Computation

    Graf, Thomas

    Abstract Reference-set constraints (RCs; also known as transderivational constraints) differ from standard well-formedness conditions in that for every tree, they compute a set of output candidates called its reference set and pick from said set the optimal candidate(s) according to some economy …

    read more
  31. Lost in Translation: A Formal Model of Merge-over-Move and Its Implications for the Language Faculty

    Graf, Thomas

    Abstract I demonstrate that Merge-over-Move (MOM), a transderivational constraint (TC) put forward in Chomsky (1995, 2000), can be modeled by linear tree transducers, i.e.\ machines that take a tree as input and traverse it from the leaves towards the root while at …

    read more
  32. Syntax, Semantics, Pragmatics: Where Do We Find Optimality?

    Graf, Thomas

    Files [pdf] [code]

    @Misc{Graf10Goettingentalk,
      author    = {Graf, Thomas},
      title     = {Syntax, Semantics, Pragmatics: {W}here do we Find
              Optimality?},
      year      = {2010},
      note      = {Invited talk, December 15, Institut für Anglistik,
              Universität Göttingen, Göttingen, Germany}
    }
    
    read more
  33. Optimality Conditions Could Care Less About Optimality

    Graf, Thomas

    Files [pdf] [code]

    @Misc{Graf10ZAStalk,
      author    = {Graf, Thomas},
      title     = {Optimality Conditions Could Care Less About Optimality},
      year      = {2010},
      note      = {Invited talk, December 10, Zentrum für Allgemeine
              Sprachwissenschaft (ZAS), Berlin, Germany}
    }
    
    read more
  34. Reference-Set Computation = Minimalism + Transformational Rules?

    Graf, Thomas

    Abstract Transderivational constraints (TC) formed an integral part of the early Minimalist Program. I develop a formal model of TCs firmly rooted in automata theory and subsequently argue that

    • in general, TCs aren’t computationally intractable, nor does their complexity exceed that of …
    read more
  35. Efficient Computation at the Interfaces

    Graf, Thomas

    Files [pdf] [code]

    @Misc{Graf10ONLIposter,
      author    = {Graf, Thomas},
      title     = {Efficient Computation at the Interfaces},
      year      = {2010},
      note      = {Poster presented at On Linguistic Interfaces II (OnLI II),
              December 2--4, 2010, University of Ulster, Belfast, United
              Kingdom}
    }
    
    read more
  36. Reference-Set Constraints as Linear Tree Transductions via Controlled Optimality Systems

    Graf, Thomas

    Abstract Reference-set constraints are a special class of constraints used in Minimalist syntax. They extend the notion of well-formedness beyond the level of single trees: When presented with some phrase structure tree, they compute its set of competing output candidates and determine the …

    read more
  37. Concealed Reference-Set Computation or How Syntax Escapes the Parser’s Clutches

    Graf, Thomas

    Abstract A core assumption of the biolinguistic program is that all properties of language beyond recursion can be motivated by requirements imposed by other cognitive modules. One component in this setup is the parser, which is thought to give rise to a preference …

    read more
  38. Locality in Flux —- Reducibility Results for Syntactic Constraints

    Graf, Thomas

    Abstract Müller and Sternefeld (2000) propose a locality hierarchy of syntactic constraints such that {representational, derivational} < global < translocal < transderivational. We use formal methods to demonstrate that their hierarchy correctly assumes that higher constraint classes are more powerful, but we also show that for …

    read more
  39. Some Interdefinability Results for Syntactic Constraint Classes

    Graf, Thomas

    Abstract Choosing as my vantage point the linguistically motivated Müller-Sternefeld hierarchy (Müller and Sternefeld 2000), which classifies constraints according to their locality properties, I investigate the interplay of various syntactic constraint classes on a formal level. For non-comparative constraints, I use Rogers’ (2003 …

    read more
  40. Towards a Factorization of String-Based Phonology

    Graf, Thomas

    Abstract Inspired by the model-theoretic approach to phonology deployed by Kracht (2003) and Potts and Pullum (2002), I develop an extendible modal logic for the investigation of phonological theories operating on (richly annotated) string structures. In contrast to previous research in this vein …

    read more
  41. Comparing Incomparable Frameworks —- a Model Theoretic Approach to Phonology

    Graf, Thomas

    Abstract In previous work, we used techniques from mathematical logic and model theory to study and compare two phonological theories, SPE and Government Phonology. The surprising result was that Government Phonology corresponds to a very weak fragment of SPE, yet it can attain …

    read more

links

contact