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 …
More Output
- read more
A Subregular Bound on the Complexity of Lexical Quantifiers
read moreAbstract 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 …
Subregular Linguistics for Linguists
read moreAbstract Drawing from computational work that is known as the subregular program, I argue against two received views in linguistics: “phonology and syntax are very different’ and “subcategorization is a solved problem”.
-
Cognitive parallelism
Subregular notions of complexity can be applied to strings …
-
Features: More Trouble Than They’re Worth?
read moreAbstract Do contemporary syntactic theories rely on too many features? Decades of computational research have culminated in two contradictory answers:
- Yes, there are too many features because having at least two features is already one too many and brings in undesirable overgeneration.
- No …
Diagnosing Movement via the Absence of c-Command Relations
read moreAbstract Based on an earlier finding that almost all c-command dependencies amount to subregular constraints on c-strings, we argue that all exceptions to this generalization involve movement. Since regulating movement is already known to be beyond the purview of c-strings …
C-Command Dependencies as TSL String Constraints
read moreAbstract 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 …
The Computational Cost of Generalizations: An Example from Micromorphology
read moreAbstract The central concern of linguistics is to succinctly state generalizations. But as numerous linguists have pointed out over the years, generalizations do not always come for free. A formalism’s ability to account for the data does …
Case Assignment in TSL Syntax: A Case Study
read moreAbstract 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 …
Structure Sensitive Tier Projection: Applications and Formal Properties
Files
read more@InProceedings{DeSantoGraf19FG, author={De Santo, Aniello and Graf, Thomas}, editor={Bernardi, Raffaella and Kobele, Gregory and Pogodalla, Sylvain}, title={Structure Sensitive Tier Projection: Applications and Formal Properties}, booktitle={Formal Grammar}, year={2019}, publisher={Springer}, address={Berlin, Heidelberg}, pages …
Structure Sensitive Tier Projection: Applications and Formal Properties
Files
read more@misc{DeSantoGraf19FGtalk, author={De Santo, Aniello and Graf, Thomas}, title={Structure Sensitive Tier Projection: Applications and Formal Properties}, year = {2019}, note = {Slides of a talk given at the 24th Conference on Formal Grammar, August 11, Riga, Latvia} }
Working the Tail: Improving UX by Optimizing Low-Frequency Items
Files
read more@misc{Graf19Kasistotalk, author = {Graf, Thomas}, title = {Working the Tail: Improving {UX} by Optimizing Low-Frequency Items}, year = {2019}, note = {Invited talk, July 8, Kasisto Inc, New York City, New York} }
Sensing Tree Automata as a Model of Syntactic Dependencies
Files
read more@inproceedings{GrafDeSanto19MOL, title = {Sensing Tree Automata as a Model of Syntactic Dependencies}, author = {Graf, Thomas and De Santo, Aniello}, booktitle = {Proceedings of the 16th Meeting on the Mathematics of Language}, pages = {12--26}, year = {2019}, address = {Toronto, Canada}, publisher …
Sensing Tree Automata as a Model of Syntactic Dependencies
Files
read more@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 …
Subregular Syntax: The What, How, and Why
read moreAbstract 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 …
The Surprising Simplicity of Syntax: Derivation Trees, Subregular Complexity, and What It Implies for Language and Cognition
read moreAbstract 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 …
Sanskrit N-Retroflexion Is Input-Output Tier-Based Strictly Local
read moreAbstract Sanskrit /n/-retroflexion is one of the most complex segmental processes in phonology. While it is still star-free, it does not fit in any of the subregular classes that are commonly entertained in the literature. We show that when …
Sanskrit N-Retroflexion Is Input-Output Tier-Based Strictly Local
read moreAbstract Sanskrit /n/-retroflexion is one of the most complex segmental processes in phonology. While it is still star-free, it does not fit in any of the subregular classes that are commonly entertained in the literature. We show that when …
C-Command Dependencies as TSL String Constraints
read moreAbstract 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 …
Case Assignment in TSL Syntax: A Case Study
read moreAbstract 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 …
Monotonicity as an Effective Theory of Morphosyntactic Variation
read moreAbstract One of the major goals of linguistics is to delineate the possible range of variation across languages. Recent work has identified a surprising number of typological gaps in a variety of domains. In morphology, this includes stem suppletion, person pronoun syncretism, case …
Pogo Sticks and Wasps: A Skeptic’s Guide to Computational Linguistics
read moreAbstract Big Data, machine learning, and neural networks have taken NLP by storm. This talk evaluates these approaches from a critical perspective. I argue that in particular for customer-facing applications, these techniques do not perform as well as one would hope once one …
Adjunction to Movement Paths: Floating Quantifiers as the Little Brother of Parasitic Gaps
read moreAbstract 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 …
Tiers and Relativized Locality Across Language Modules
read moreAbstract Heinz and Idsardi (2013) draw attention to a profound computational difference between syntax and phonology: phonology only requires regular computations over strings (Johnson 1972 …
Why Movement Comes for Free Once You Have Adjunction
read moreAbstract This paper presents a novel answer to the question why Move might be an integral part of language. The answer is rooted in the computational framework of subregular complexity, which has already been fruitfully applied to phonology. The computational perspective reveals that …
- read more
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 treats all …
Derivations as Representations: News from the Computational Frontier
read moreAbstract Ever since McCawley (1968) one of the fundamental questions of linguistic theory has been whether formalisms should be construed as derivational or representational in nature. The former focuses on how structures are built in an incremental fashion from pre-defined atoms via structure-building …
Grammar Size and Quantitative Restrictions on Movement
read moreAbstract 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 …
Grammar Size and Quantitative Restrictions on Movement
read moreAbstract 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 …
One Reason to Move, a Million Reasons to Be an Island: Third-Factor Explanations from Computational Syntax
read moreAbstract Two linguistic findings are commonly taken for granted yet are anything but trivial:
- Phrases can be displaced from their base position.
- Some phrases block displacement.
On a technical level, these properties are hashed out in terms of movement and islands. From a …
Subregular Morpho-Semantics: The Expressive Limits of Monomorphemic Quantifiers
read moreAbstract Even though languages are capable of expressing very complex generalized quantifiers such as all but seven and an even number of, the range of possible meanings for monomorphemic determiners seems to be limited to every, no, some, and numerals. In this talk …
Locality Domains and Phonological c-Command over Strings
read moreAbstract 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 …
Syntax in Phonology? C-Command over Strings
Evaluating Subregular Distinctions in the Complexity of Generalized Quantifiers
read moreAbstract Semantic automata were developed to compare the complexity of generalized quantifiers based on the complexity of the string languages that describe their truth conditions. An important point that has gone unnoticed so far is that …
Graph Transductions and Typological Gaps in Morphological Paradigms
read moreAbstract 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 …
Graph Transductions and Typological Gaps in Morphological Paradigms
read moreAbstract 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 …
Do We Need Features for Morphosyntax?
read moreAbstract 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 …
It’s a (Sub-)Regular Conspiracy: Locality and Computation in Phonology, Morphology, Syntax, and Semantics
read moreAbstract 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 …
The Power of Locality Domains in Phonology
read moreAbstract Domains play an integral role in linguistic theories. This paper combines locality domains with current work on the computational complexity of phonology. The first result is that if a specific formalism —- Strictly Piecewise (SP) grammars —- is supplemented with a mechanism to enforce …
Relative Clauses as a Benchmark for Minimalist Parsing
read moreAbstract Minimalist grammars have been used recently in a series of papers to explain well-known contrasts in human sentence processing in terms of subtle structural differences. These proposals combine a top-down parser with complexity metrics that relate parsing …
Fragments of First-Order Logic for Linguistic Structures
read moreAbstract Logic has always played a central role in the study of natural language meaning. But logic can also be used to describe the structure of words and sentences. Recent research has revealed that these structures are so simple that they can be …
Computational Parallels Across Language Modules
read moreAbstract 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 …
A Single Movement Normal Form for Minimalist Grammars
read moreAbstract Movement is the locus of power in Minimalist grammars (MGs) but also their primary source of complexity. In order to simplify future analysis of the formalism, we prove that every MG can be converted into a …
Morphotactics as Tier-Based Strictly Local Dependencies
read moreAbstract 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 …
Morphotactics as Tier-Based Strictly Local Dependencies
read moreAbstract 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 …
An Alternate View on Strong Lexicalization in TAG
read moreAbstract 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 …
A Computational Guide to the Dichotomy of Features and Constraints
read moreAbstract A contentious issue in the Minimalist literature is whether certain phenomena are best described in terms of features or constraints. Building on recent work in mathematical linguistics, I argue that constraints and features are interchangeable in Minimalist syntax. This does not invalidate …
A Single Movement Normal Form for Minimalist Grammars
read moreAbstract Movement is the locus of power in Minimalist grammars (MGs) but also their primary source of complexity. In order to simplify future analysis of the formalism, we prove that every MG can be converted into a …
An Alternate View on Strong Lexicalization in TAG
read moreAbstract 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 …
Computational Lessons from and for Language
read moreAbstract Barely any task is more challenging and more effortlessly carried out by humans than the efficient use of language. Within a couple of years, children figure out a learning problem that even computers with large, extensively annotated training sets fail at. On …
Memory Usage Predicts Relative Difficulty in Human Sentence Processing
Tier-Based Strict Locality in Phonology and Morphology
Files
read more@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 …
Towards an Algebraic Morphosyntax
read moreAbstract I argue that important generalizations in morphosyntax are currently obscured by the technical details of the syntactic apparatus. These generalizations can be brought out more clearly via a perspective that is informed by higher algebra.
I support my argument with a case …
Computational Unity Across Language Modules
read moreAbstract Computational linguistics is often construed as the enterprise of processing language with computers. But the field has much more to offer than just that. A computationally informed perspective of language offers profound scientific insights and can unearth new language universals. In this …
Adjuncts, Conjuncts, Ojuncts: Deriving Strong Island Constraints
read moreAbstract 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 …
Syntax and Phonology: A Computational Common Core
Files
read more@Misc{Graf15StPetetalk, author = {Graf, Thomas}, title = {Syntax and Phonology: {A} Computational Common Core}, year = {2015}, note = {Department of Mathematical Linguistics, Saint Petersburg State University, St. Petersburg, Russia} }
Formal Processing Theory, or Parsing Without Parsers
read moreAbstract I argue that computational parsing research so far has operated at the wrong level(s) of granularity and that we should take a hint from formal language theory instead. Rather than compare the predictions of specific parsing models for specific phenomena, we …
A Refined Notion of Memory Usage for Minimalist Parsing
read moreAbstract 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 …
A Refined Notion of Memory Usage for Minimalist Parsing
read moreAbstract 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 …
A Hidden Consensus: Computational Invariants of Minimalist Syntax
read moreAbstract 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 …
Commonality in Disparity: The Computational View of Syntax and Phonology
read moreAbstract 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 …
A Computational Guide to the Dichotomy of Features and Constraints
read moreAbstract 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 …
Dependencies in Syntax and Phonology: A Computational Comparison
Adjuncts, Islands, Algebra (with a Sprinkling of Semantics)
Models of Adjunction in Minimalist Grammars
read moreAbstract 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 …
Models of Adjunction in Minimalist Grammars
read moreAbstract 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 …
Evaluating Evaluation Metrics for Minimalist Parsing
read moreAbstract In response to Kobele et al. (2012), we evaluate four ways of linking the processing difficulty of sentences to the behavior of the top-down parser for Minimalist grammars developed in Stabler (2012). We investigate the predictions these four metrics …
Evaluating Evaluation Metrics for Minimalist Parsing
read moreAbstract In response to Kobele et al. (2012), we evaluate four ways of linking the processing difficulty of sentences to the behavior of the top-down parser for Minimalist grammars developed in Stabler (2012). We investigate the predictions these four metrics …
Late Merge as Lowering Movement in Minimalist Grammars
read moreAbstract Minimalist grammars can be specified in terms of their derivation tree languages and a mapping from derivations to derived trees, each of which is definable in monadic second-order logic (MSO). It has been shown that the linguistically motivated operation Late Merge can …
Late Merge as Lowering Movement in Minimalist Grammars
read moreAbstract Minimalist grammars can be specified in terms of their derivation tree languages and a mapping from derivations to derived trees, each of which is definable in monadic second-order logic (MSO). It has been shown that the linguistically motivated operation Late Merge can …
Feature Geometry and the Person Case Constraint: An Algebraic Link
read moreAbstract 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 …
Feature Geometry and the Person Case Constraint: An Algebraic Link
read moreAbstract 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 …
Person Case Constraints and Feature Complexity in Syntax
Beyond the Apparent: Cognitive Parallels Between Syntax and Phonology
read moreAbstract One of the central changes in 20th century linguistics was the reconceptualization of language as a cognitive ability rather than merely an abstract relational system of signs —- in the terminology of Chomsky (1986), the move from E-language to I-language. This shift entails …
Optionality Implies Islandhood
Islands Without Islands
Computational Computational Linguistics
Local and Transderivational Constraints in Syntax and Semantics
read moreAbstract A long-standing tension in Minimalist syntax is that between the structure-building operations Merge and Move on the one hand and the constraints restricting the shape of the structures built by said operations on the other. Proposals differ vastly in how much weight …
The Syntactic Algebra of Adjuncts
read moreAbstract This paper gives a theory-neutral account of the Adjunct Island Constraint. I show that the island status of adjuncts is a consequence of two properties that set them apart from arguments: optionality and independence. Adjuncts can be omitted without affecting grammaticality, and …
The Syntactic Algebra of Adjuncts
read moreAbstract 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 …
The Price of Freedom: Why Adjuncts Are Islands
read moreAbstract I propose that if one takes seriously the Minimalist idea that syntax is driven by Merge and the feature calculus, the status of adjuncts as strong islands follows immediately from the properties that set them apart from arguments: optionality and iterability. This …
Constraints Emerge from Merge
Of Tops and Bottoms: The Algebra of Person Case Constraints
read moreAbstract 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 …
Tree Adjunction as Minimalist Lowering
read moreAbstract Even though Minimalist grammars are more powerful than TAG on the string level, the classes of tree languages the two define are incomparable. I give a constructive proof that if the standard Move operation in Minimalist grammars is replaced by Reset Lowering …
Tree Adjunction as Minimalist Lowering
read moreAbstract TAG and Minimalist grammars (MGs) are related in very interesting ways. Even though MGs subsume TAGs at the level of string languages, their respective classes of tree languages are incomparable (Kobele et al 2007, Mönnich 2006). As pointed out by Mönnich (2006 …
Is Syntactic Binding Rational?
read moreAbstract Recent results show that both TAG and Minimalist grammars can be enriched with rational constraints without increasing their strong generative capacity, where a constraint is rational iff it can be computed by a bottom-up tree automaton. This raises the …
Is Syntactic Binding Rational?
read moreAbstract Recent results show that both TAG and Minimalist grammars can be enriched with rational constraints without increasing their strong generative capacity, where a constraint is rational iff it can be computed by a bottom-up tree automaton. This raises the …
Movement-Generalized Minimalist Grammars
read moreAbstract 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 …
Movement-Generalized Minimalist Grammars
read moreAbstract 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 …
Binding Complexity and the Status of Pronouns in English and Asl
read moreAbstract We have argued in previous work based on data from English that Principle B is suspended in all those contexts that would allow for an unbounded number of pronouns to occur within a single binding domain. American Sign Language …
The Complexity of Binding in English and ASL
read moreAbstract It is a well-known fact that pronouns can sometimes be locally bound in English, for instance in picture-phrases and certain adjuncts. Even though many different analyses have been developed over the years, it is still unclear why English …
Why There Must Be Exceptions to Principle B
read moreAbstract Recent Minimalist thinking has been strongly influenced by the idea that some universals may be due to factors outside the language faculty, in particular limited computational resources (Chomsky 2005). In combination with recent results on Stablerian Minimalist grammars (Stabler 1997, Graf 2011 …
Concealed Reference-Set Computation: How Syntax Escapes the Parser’s Clutches
read moreAbstract It has been conjectured that all properties of language beyond recursion can be motivated by interface requirements. One component in this setup is the parser, which is thought to give rise to a preference for computational parsimony. I discuss a mathematical result …
An Algebraic Perspective on the Person Case Constraint
read moreAbstract Graf (2011) and Kobele (2011) proved independently that Minimalist grammars can express all constraints that are definable in weak monadic second-order logic (MSO), i.e. the extension of first-order logic with quantification over finite sets. The proof takes as its vantage point …
Theories of Everything. In Honor of Ed Keenan
Locality and the Complexity of Minimalist Derivation Tree Languages
read moreAbstract 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 …
Locality and the Complexity of Minimalist Derivation Tree Languages
read moreAbstract 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 …
Closure Properties of Minimalist Derivation Tree Languages
read moreAbstract 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 …
Closure Properties of Minimalist Derivation Tree Languages
read moreAbstract 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 …
Optimality Is Not a Race: Against a Performance-Based View of Reference-Set Computation
read moreAbstract 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 …
Lost in Translation: A Formal Model of Merge-over-Move and Its Implications for the Language Faculty
read moreAbstract 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 …
Syntax, Semantics, Pragmatics: Where Do We Find Optimality?
Optimality Conditions Could Care Less About Optimality
Reference-Set Computation = Minimalism + Transformational Rules?
read moreAbstract 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 …
Efficient Computation at the Interfaces
Rethinking Transderivationality
read moreAbstract 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 …
Logics of Phonological Reasoning
read moreAbstract Inspired by Kracht (2003) and Potts and Pullum (2002), who use tools from mathematical logic in their investigation of phonological theories, I develop an extendable modal logic over string structures, which in turn is used to formalize a specific phonological theory, Government …
Reference-Set Constraints as Linear Tree Transductions via Controlled Optimality Systems
read moreAbstract 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 …
Reference-Set Constraints as Linear Tree Transductions via Controlled Optimality Systems
read moreAbstract 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 …
Concealed Reference-Set Computation or How Syntax Escapes the Parser’s Clutches
read moreAbstract 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 …
Formal Parameters of Phonology: From Government Phonology to SPE
read moreAbstract Inspired by the model-theoretic approach to phonology deployed by Kracht (2003) and Potts and Pullum (2002), I develop an extendable modal logic for the investigation of phonological theories operating on (richly annotated) string structures. In contrast to previous research in this vein …
Some Interdefinability Results for Syntactic Constraint Classes
read moreAbstract 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 …
Comparing Incomparable Frameworks: A Model Theoretic Approach to Phonology
read moreAbstract 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 …
A Tree Transducer Model of Reference-Set Computation
read moreAbstract 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 …
Papers in Mathematical Linguistics 1
Locality in Flux —- Reducibility Results for Syntactic Constraints
read moreAbstract 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 …
Some Interdefinability Results for Syntactic Constraint Classes
read moreAbstract 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 …
Towards a Factorization of String-Based Phonology
read moreAbstract 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 …
Towards a Factorization of String-Based Phonology
read moreAbstract 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 …
Comparing Incomparable Frameworks —- a Model Theoretic Approach to Phonology
read moreAbstract 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 …
Ein Modelltheoretischer Blick Auf Syntaktische Constraints
From Vagueness to Disaster: On the Intricacies of Feature Checking
read moreAbstract Because the thesis I wrote as a wee undergrad at the University of Vienna is cited in Reuland (2011) Anaphora and Language Design, I finally decided to upload it despite its many shortcomings. The (preachy) message is that we have to be …
Agreement with Hybrid Nouns in Icelandic
Abstract A short squib on the special gender agreement properties exhibited by Icelandic nouns when their semantic gender is different from their syntactic gender.
Files [pdf]
read more@Article{Graf07Snippets, author = {Graf, Thomas}, title = {Agreement with Hybrid Nouns in {I}celandic}, year = {2007}, journal = {Snippets …