An official website of the United States government
Semantic automata were developed to compare the complexity of generalized quantifiers in terms of the string languages that describe their truth conditions. An important point that has gone unnoticed so far is that these string languages are remarkably simple for most quantifiers, in particular those that can be realized by a single lexical item. Whereas complex quantifiers such as "an even number of" correspond to specific regular languages, the lexical quantifiers "every", "no", "some", as well as numerals do not reach this level of complexity. Instead, they all stay close to the bottom of the so-called subregular hierarchy. What more, the class of tier-based strictly local languages provide a remarkably tight characterization of the class of lexical quantifiers. A significant number of recent publications have also argued for the central role of tier-based strict locality in phonology, morphology, and syntax. This suggests that subregularity in general and tier-based strict locality in particular may be a unifying property of natural language across all its submodules.
more »
« less
Morphologically simplex D-quantifiers are strictly 2-local
Even though languages can express a wide range of quantifiers, only a small number are ever realized as morphologically simplex determiners: every, no, some, and most. This is puzzling because I) most is much more complex than the other three, and II) quantifiers like an even number are simpler than most yet cannot belong to this class. Building on concepts from subregular complexity, I present a new way of measuring a quantifier’s complexity in terms of its verification pattern. The quantifiers every, no, some, and most all have strictly 2-local (SL-2) verification patterns, but quantifiers like an even number do not. This suggests that subregular complexity, and in particular strict locality, plays a crucial role for how much meaning can be packed into morphologically simplex expressions.
more »
« less
- Award ID(s):
- 1845344
- PAR ID:
- 10608496
- Publisher / Repository:
- University of Massachusetts Amherst Libraries
- Date Published:
- Journal Name:
- Proceedings of SCiL 2024
- ISSN:
- 2834-1007
- Subject(s) / Keyword(s):
- generalized quantifiers semantic automata subregular complexity morphosemantics strict locality
- Format(s):
- Medium: X
- Right(s):
- Creative Commons Attribution 4.0
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Mulzer, Wolfgang; Phillips, Jeff M (Ed.)Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing pairwise distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x₁, x₂) ≤ d(x₁, y) + d(y, x₂) to the "simplex inequality" d(x_1, …, x_k) ≤ ∑_{i=1}^k d(x_1, …, x_{i-1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into 𝓁_∞) and isometric embedding of all tree metrics into 𝓁₁. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics.more » « less
-
We introduce an abstract and strong model of massively parallel computation, where essentially the only restrictions are that the “fan-in” of each machine is limited to s bits, where s is smaller than the input size n, and that computation proceeds in synchronized rounds, with no communication between different machines within a round. Lower bounds on round complexity in this model apply to every computing platform that shares the most basic design principles of MapReduce-type systems. We apply a variant of the “polynomial method” to capture restrictions obeyed by all such massively parallel computations. This connection allows us to translate a lower bound on the (approximate) polynomial degree of a Boolean function to a lower bound on the round complexity of every (randomized) massively parallel computation of that function. These lower bounds apply even in the “unbounded width” version of our model, where the number of machines can be arbitrarily large. As one example of our general results, computing any non-trivial monotone graph property — such as any of the standard connectivity problems — requires a super-constant number of rounds when every machine can accept only a sub-polynomial (in n) number of input bits s. This lower bound constitutes significant progress on a major open question in the area,more » « less
-
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 is most succinctly analyzed in terms of the formal class TSL. Any cognitive device that can handle this level of complexity also possesses sufficient resources for Move. In fact, Merge and Move are remarkably similar instances of TSL. Consequently, Move has little computational or conceptual cost attached to it and comes essentially for free in any grammar that expresses Merge as compactly as possible.more » « less
-
The subregular approach has revealed that the phonological surface patterns found in natural language are much simpler than previously assumed. Most patterns belong to the subregular class of tier-based strictly local languages (TSL), which characterizes them as the combination of a strictly local dependency with a tier-projection mechanism that masks out irrelevant segments. Some non-TSL patterns have been pointed out in the literature, though. We show that these outliers can be captured by rendering the tier projection mechanism sensitive to the surrounding structure. We focus on a specific instance of these structure-sensitive TSL languages: input-local TSL (ITSL), in which the tier projection may distinguish between identical segments that occur in different local contexts in the input string. This generalization of TSL establishes a tight link between tier-based language classes and ISL transductions, and is motivated by several natural language phenomena.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.7275/scil.2127
