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 …
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 …
- 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 …
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 …