An official website of the United States government
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 trees (e.g. constraints on tree tiers) can be reduced to such strings. We define serial constraints as an abstraction that decomposes string constraints into a context function (which associates nodes with strings) and a requirement function (which enforces constraints on these strings). We provide a general procedure for implementing serial constraints as deterministic tree automata. The construction reveals that the many types of constraints found in subregular syntax are variants of the same computational template. Our findings open up a string-based perspective on syntactic constraints and provide a new, very general approach to the automata-theoretic study of subregular complexity.
more »
« less
On stretch-limited elastic strings
Motivated by the increased interest in modelling non-dissipative materials by constitutive relations more general than those from Cauchy elasticity, we initiate the study of a class of stretch-limited elastic strings : the string cannot be compressed smaller than a certain length less than its natural length nor elongated larger than a certain length greater than its natural length. In particular, we consider equilibrium states for a string suspended between two points under the force of gravity (catenaries). We study the locations of the supports resulting in tensile states containing both extensible and inextensible segments in two situations: the degenerate case when the string is vertical and the non-degenerate case when the supports are at the same height. We then study the existence and multiplicity of equilibrium states in general with multiplicity differing markedly from strings satisfying classical constitutive relations.
more »
« less
- Award ID(s):
- 1703180
- PAR ID:
- 10377818
- Date Published:
- Journal Name:
- Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
- Volume:
- 477
- Issue:
- 2249
- ISSN:
- 1364-5021
- Page Range / eLocation ID:
- 20210181
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This study proposes a simple and novel class of stretch-limiting constitutive relations for perfectly flexible elastic strings drawn from modern advances in constitutive theory for elastic bodies. We investigate strings governed by constitutive relations where stretch is a bounded, piecewise linear function of tension, extending beyond the traditional Cauchy elasticity framework. Our analysis includes explicit solutions for catenaries and longitudinal, piecewise constant stretched motions.more » « less
-
Real-time decision making in IoT applications relies upon space-efficient evaluation of queries over streaming data. To model the uncertainty in the classification of data being processed, we consider the model of probabilistic strings --- sequences of discrete probability distributions over a finite set of events, and initiate the study of space complexity of streaming computation for different classes of queries over such probabilistic strings. We first consider the problem of computing the probability that a word, sampled from the distribution defined by the probabilistic string read so far, is accepted by a given deterministic finite automaton. We show that this regular pattern matching problem can be solved using space that is only poly-logarithmic in the string length (and polynomial in the size of the DFA) if we are allowed a multiplicative approximation error. Then we show how to generalize this result to quantitative queries specified by additive cost register automata --- these are automata that map strings to numerical values using finite control and registers that get updated using linear transformations. Finally, we consider the case when updates in such an automaton involve tests, and in particular, when there is a counter variable that can be either incremented or decremented but decrements only apply when the counter value is non-zero. In this case, the desired answer depends on the probability distribution over the set of possible counter values that can range from 0 to n for a string of length n. Under a mild assumption, namely probabilities of the individual events are bounded away from 0 and 1, we show that there is an algorithm that can compute all n entries of this probability distribution vector to within additive 1/poly(n) error using space that is only Õ(n). In establishing these results, we introduce several new technical ideas that may prove useful for designing space-efficient algorithms for other query models over probabilistic strings.more » « less
-
Abstract One-dimensional strings of local excitations are a fascinating feature of the physical behavior of strongly correlated topological quantum matter. Here we study strings of local excitations in a classical system of interacting nanomagnets, the Santa Fe Ice geometry of artificial spin ice. We measured the moment configuration of the nanomagnets, both after annealing near the ferromagnetic Curie point and in a thermally dynamic state. While the Santa Fe Ice lattice structure is complex, we demonstrate that its disordered magnetic state is naturally described within a framework of emergent strings. We show experimentally that the string length follows a simple Boltzmann distribution with an energy scale that is associated with the system’s magnetic interactions and is consistent with theoretical predictions. The results demonstrate that string descriptions and associated topological characteristics are not unique to quantum models but can also provide a simplifying description of complex classical systems with non-trivial frustration.more » « less
-
A bstract We discuss aspects of the possible transition between small black holes and highly excited fundamental strings. We focus on the connection between black holes and the self gravitating string solution of Horowitz and Polchinski. This solution is interesting because it has non-zero entropy at the classical level and it is natural to suspect that it might be continuously connected to the black hole. Surprisingly, we find a different behavior for heterotic and type II cases. For the type II case we find an obstruction to the idea that the two are connected as classical solutions of string theory, while no such obstruction exists for the heterotic case. We further provide a linear sigma model analysis that suggests a continuous connection for the heterotic case. We also describe a solution generating transformation that produces a charged version of the self gravitating string. This provides a fuzzball-like construction of near extremal configurations carrying fundamental string momentum and winding charges. We provide formulas which are exact in α ′ relating the thermodynamic properties of the charged and the uncharged solutions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1098/rspa.2021.0181
