Results 21 to 30 of about 649 (143)
Morphology Matters: A Multilingual Language Modeling Analysis
Transactions of the Association for Computational Linguistics, 2021 Prior studies in multilingual language modeling (e.g., Cotterell et al., 2018; Mielke et al., 2019) disagree on whether or not inflectional morphology makes languages harder to model. We attempt to resolve the disagreement and extend those studies.
Hyunji Hayley Park +5 more
doaj +1 more source
What neural networks know about linguistic complexity
Russian Journal of Linguistics, 2022 Linguistic complexity is a complex phenomenon, as it manifests itself on different levels (complexity of texts to sentences to words to subword units), through different features (genres to syntax to semantics), and also via different tasks (language ...
Serge Aleksandrovich Sharoff
doaj +1 more source
Subword Complexity and k-Synchronization [PDF]
, 2013 We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-automatic. As an application, we generalize recent results of Goldstein. We give analogous results for the number of distinct factors of length n that are primitive words or ...
Daniel Goc +2 more
openaire +2 more sources
On Minimal Words With Given Subword Complexity [PDF]
The Electronic Journal of Combinatorics, 1998 We prove that the minimal length of a word $S_n$ having the property that it contains exactly $F_{m+2}$ distinct subwords of length $m$ for $1 \leq m \leq n$ is $F_n + F_{n+2}$. Here $F_n$ is the $n$th Fibonacci number defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$.
Ming-wei Wang, Jeffrey O. Shallit
openaire +2 more sources
The height of piecewise-testable languages and the complexity of the logic of subwords [PDF]
Logical Methods in Computer Science, 2019 The height of a piecewise-testable language $L$ is the maximum length of the words needed to define $L$ by excluding and requiring given subwords. The height of $L$ is an important descriptive complexity measure that has not yet been investigated in a ...
Prateek Karandikar, Philippe Schnoebelen
doaj +1 more source
Arithmetical subword complexity of automatic sequences
CoRR, 2023 We fully classify automatic sequences $a$ over a finite alphabet $Ω$ with the property that each word over $Ω$ appears is $a$ along an arithmetic progression. Using the terminology introduced by Avgustinovich, Fon-Der-Flaass and Frid, these are the automatic sequences with the maximal possible arithmetical subword complexity.
Jakub Konieczny, Clemens Müllner
openaire +2 more sources
The Maximal Complexity of Quasiperiodic Infinite Words
Axioms, 2021 A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod.
Ludwig Staiger
doaj +1 more source
Subword Complexity and Decomposition of the Set of Factors [PDF]
, 2014 In this paper we explore a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class $L_k$ if it is a subset of the catenation of $k$ languages $S_1\cdots S_k$, where the number of words of length $n$ in each of $S_i$ is bounded by a constant.
Cassaigne, Julien +3 more
openaire +4 more sources
Subword complexes and edge subdivisions [PDF]
Proceedings of the Steklov Institute of Mathematics, 2014 For a finite Coxeter group, a subword complex is a simplicial complex associated with a pair (Q, π), where Q is a word in the alphabet of simple reflections, $π$ is a group element. We discuss the transformations of such a complex induced by braid moves of the word Q.
openaire +3 more sources
Subword complexes in Coxeter groups
Advances in Mathematics, 2004 Let (Π,Σ) be a Coxeter system. An ordered list of elements in Σand an element in Πdetermine a {\em subword complex}, as introduced in our paper on Gröbner geometry of Schubert polynomials (math.AG/0110058). Subword complexes are demonstrated here to be homeomorphic to balls or spheres, and their Hilbert series are shown to reflect combinatorial ...
Knutson, Allen, Miller, Ezra
openaire +3 more sources