Abstract Based on a formal analysis of the operations Merge and Move, I provide a computational answer to the question why Move might be an integral part of language. The answer is rooted in the framework of subregular complexity, which reveals that Merge …
More Output
- read more
Diving Deeper into Subregular Syntax
read moreAbstract In my target paper Subregular linguistics: Bridging theoretical linguistics and formal grammar I argued that theoretical linguistics and formal grammar, despite major differences in methodology, have a lot to offer to each other, and that the recently emerged subfield of subregular linguistics …
Subregular Linguistics: Bridging Theoretical Linguistics and Formal Grammar
read moreAbstract Subregular linguistics is a fairly new approach that seeks a deeper understanding of language by combining the rigor of formal grammar with the empirical sophistication of theoretical linguistics. The approach started in phonology but has since branched out to morphology and even …
Linguistics and Symbolic Computation in a World of Large Language Models
read moreAbstract Language has always played a central role in artificial intelligence, yet AI researchers and linguists have rarely seen eye to eye on things, in particular the status of subsymbolic/neural approaches to language. After decades of debates, it looks like the subsymbolic …
Subregular Tree Transductions, Movement, Copies, Traces, and the Ban on Improper Movement
read moreAbstract Extending prior work in Graf (2018, 2020, 2022c), I show that movement is tier-based strictly local (TSL) even if one analyzes it as a transformation, i.e. a tree transduction from derivation trees to output trees. I define input strictly local (ISL …
Subregular Tree Transductions, Movement, Copies, Traces, and the Ban on Improper Movement
read moreAbstract Extending prior work in Graf (2018, 2020, 2022c), I show that movement is tier-based strictly local (TSL) even if one analyzes it as a transformation, i.e. a tree transduction from derivation trees to output trees. I define input strictly local (ISL …
The Dose Makes the Poison: Chesi’s Vision and Subregular Syntax
read moreAbstract In this reply to Chesi’s Is it the end of (generative) linguistics as we know it, I argue that the specifics of his vision for generative syntax in the 21st century remain hazy. Depending on how one interprets Chesi’s methodological …
Automata for Subregular Syntax: Syntax with Strings Attached
read moreAbstract Building on recent work in subregular syntax, we argue that syntactic constraints are best understood as operating not over trees, but rather strings that track structural relations such as dominance and c-command. Even constraints that seem intrinsically tied to …
Multiple Wh-Movement Is Not Special: The Subregular Complexity of Persistent Features in Minimalist Grammars
read moreAbstract Minimalist grammars have been criticized for their inability to analyze successive cyclic movement and multiple wh-movement in a manner that is faithful to the Minimalist literature. Persistent features have been proposed in the literature as a potential remedy (Stabler …
Multiple Wh-Movement Is Not Special: The Subregular Complexity of Persistent Features in Minimalist Grammars
read moreAbstract Minimalist grammars have been criticized for their inability to analyze successive cyclic movement and multiple wh-movement in a manner that is faithful to the Minimalist literature. Persistent features have been proposed in the literature as a potential remedy (Stabler …
Diagnosing Movement via the Absence of c-Command Relations
read moreAbstract In this paper, we propose a new diagnostic for movement. It has been argued in the computational linguistics literature that some constraints can be formalized by path constraints on the sequence of their c-commanders (Graf and Shafiei 2019), and …
The Subregular Complexity of Syntactic Islands
read moreAbstract We provide a formal framework for analyzing syntactic island effects from a subregular perspective. Key aspects of the syntactic representation are encoded as strings where precedence represents containment. Island effects then are expressed as constraints on the shape of …
The Subregular Complexity of Syntactic Islands
read moreAbstract We provide a formal framework for analyzing syntactic island effects from a subregular perspective. Key aspects of the syntactic representation are encoded as strings where precedence represents containment. Island effects then are expressed as constraints on the shape of …
Are Syntactic Categories ISL-2 Inferrable? A Corpus Study
read moreAbstract We use the MG treebank of Torr (2017) to investigate the conjecture in Graf (2020) that category systems are ISL-2 inferrable. A category system is ISL-2 inferrable iff the category feature of every lexical item …
Modeling Island Effects with Probabilistic Tier-Based Strictly Local Grammars over Trees
read moreAbstract We fuse two recent strands of work in subregular linguistics—probabilistic tier projections (Mayer, 2021) and tier-based perspectives on movement (Graf, 2022a)—into a probabilistic model of syntax that makes it easy to add gradience …
Modeling Island Effects with Probabilistic Tier-Based Strictly Local Grammars over Trees
read moreAbstract We fuse two recent strands of work in subregular linguistics—probabilistic tier projections (Mayer, 2021) and tier-based perspectives on movement (Graf, 2022a)—into a probabilistic model of syntax that makes it easy to add gradience …
Syntactic Tiers for Movement and Agreement
read moreAbstract This lecture series is an empirically minded introduction to the concept of tiers, which for the last ten year has played a central role in work at the intersection of theoretical and computational linguistics. While this computational notion of tiers is inspired …
The Computational Nature of Language
read moreAbstract This course is aimed at students with the general mathematical maturity that can be expected of ESSLLI students (sets, functions, relations, first-order logic), but no further background in linguistics or the theory of computation. It uses recent ideas from subregular complexity, formalized …
Subregular Linguistics for…well, Linguists
read moreAbstract Subregular linguistics is a recent research program that draws heavily from formal language theory but enjoys two noteworthy traits:
- the key concepts are intuitive and easy to visualize without the use of any mathematics, and
- its computational machinery is very sensitive to …
Curbing Feature Coding: Strictly Local Feature Assignment
read moreAbstract Graf (2017) warns that every syntactic formalism faces a severe overgeneration problem because of the hidden power of subcategorization. Any constraint definable in monadic second-order logic can be compiled into the category system so that it is indirectly enforced as part of …
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 …
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 …
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 …
Sensing Tree Automata as a Model of Syntactic Dependencies
read moreAbstract Various aspects of syntax have recently been characterized in subregular terms. However, these characterizations operate over very different representations, including string encodings of c-command relations as well as tiers projected from derivation trees. We present a way to …
Sensing Tree Automata as a Model of Syntactic Dependencies
read moreAbstract Various aspects of syntax have recently been characterized in subregular terms. However, these characterizations operate over very different representations, including string encodings of c-command relations as well as tiers projected from derivation trees. We present a way to …
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 …
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 …
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 …
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
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 …
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 …
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 …
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 …
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} }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 …
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 …