Determining whether an unknown distribution matches a known reference is a cornerstone problem in distributional analysis. While classical results establish a rigorous framework in the case of distributions over finite domains, real-world applications in computational linguistics, bioinformatics, and program analysis demand testing over infinite combinatorial structures, particularly strings. In this paper, we initiate the theoretical study of identity testing for stochastic languages, bridging formal language theory with modern distribution property testing. We first propose a polynomial-time algorithm to verify if a finite state machine represents a stochastic language, and then prove that rational stochastic languages can approximate an arbitrary probability distribution. Building on these representations, we develop a truncation-based identity testing algorithm that distinguishes between a known and an unknown distributions with sample complexity $\widetildeΘ\left( \frac{\sqrt{n}}{\varepsilon^2} + \frac{n}{\log n} \right)$ where $n$ is the size of the truncated support. Our approach leverages the exponential decay inherent in rational stochastic languages to bound truncation error, then applies classical finite-domain testers to the restricted problem. This work establishes the first identity testing framework for infinite discrete distributions, opening new directions in probabilistic formal methods and statistical analysis of structured data.
Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin
We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.
Nicolas van Kempen, Hyuk-Je Kwon, Dung Tuan Nguyen
et al.
Does the choice of programming language affect energy consumption? Previous highly visible studies have established associations between certain programming languages and energy consumption. A causal misinterpretation of this work has led academics and industry leaders to use or support certain languages based on their claimed impact on energy consumption. This paper tackles this causal question directly: it develops a detailed causal model capturing the complex relationship between programming language choice and energy consumption. This model identifies and incorporates several critical but previously overlooked factors that affect energy usage. These factors, such as distinguishing programming languages from their implementations, the impact of the application implementations themselves, the number of active cores, and memory activity, can significantly skew energy consumption measurements if not accounted for. We show -- via empirical experiments, improved methodology, and careful examination of anomalies -- that when these factors are controlled for, notable discrepancies in prior work vanish. Our analysis suggests that the choice of programming language implementation has no significant impact on energy consumption beyond execution time.
This thesis (Habilitation à diriger des recherches) presents some of my research contributions since my Ph.D defense in 2008. I have had the chance to participate in the development of quantum programming languages since their early developments: the presentation aims to present my point of view on the evolution of the subject, my contributions, and the current research trends in the community. The target audience is a graduate student interested in pointers to the field of quantum programming languages.
Lexical expletives can be divided into two main classes: (i) CP expletives required by the V2 constraint and, hence, by the necessity to lexicalize the position on the left of the inflected verb and (ii) TP expletives connected with the negative value of the pro-drop parameter and, therefore, with the necessity to lexicalize the ’structural‘ subject position, specifically, [Spec, TP]. The latter can, in turn, be divided into two subclasses: impersonal subjects and positional expletives, which occur with postverbal/low subjects and extraposed subject clauses. While CP expletives only appear in Germanic varieties that maintain V2, the subclassification of TP expletives yields interesting results when comparing Cimbrian and the Venetan varieties in Nord-East Italy, where the gradual disappearance of the positional expletive in free inversion structures and the residual maintenance of impersonal subjects from North to South along the Adige River confirms the distinction between two classes of subject expletives; furthermore, the resilience of impersonal subjects and their distribution in the northwestern part of the area under consideration sheds light on the role of language contact which is confirmed along the same axis—but crucially in the opposite direction—by the increasing employment of cleft constructions in WH-clauses replacing enclisis (i.e.,: pronominal subject inversion with the finite verb).
Let $c>1$ be a real constant. We say that a language $L$ is $c$-\emph{constantly growing} if for every word $u\in L$ there is a word $v\in L$ with $\vert u\vert<\vert v\vert\leq c+\vert u\vert$. We say that a language $L$ is $c$-\emph{geometrically growing} if for every word $u\in L$ there is a word $v\in L$ with $\vert u\vert<\vert v\vert\leq c\vert u\vert$. Given a language $L$, we say that $L$ is $REG$-\emph{dissectible} if there is a regular language $R$ such that $\vert L\setminus R\vert=\infty$ and $\vert L\cap R\vert=\infty$. In 2013, it was shown that every $c$-constantly growing language $L$ is $REG$-dissectible. In 2023, the following open question has been presented: "Is the family of geometrically growing languages $REG$-dissectible?" We construct a $c$-geometrically growing language $L$ that is not $REG$-dissectible. Hence we answer negatively to the open question.
Propõe-se aqui que os processos de ‘mediação’ no ensino-aprendizagem de línguas adicionais deveriam incorporar uma componente de reflexão, assumindo uma concepção de linguagem de extração não essencialista. Nota-se que no debate em curso são mobilizadas concepções anacrônicas do que seja ‘traduzir’, o que dificulta uma compreensão adequada do processo e sua (re-) incorporação nas práticas didáticas. O argumento recorre a elementos retirados de longa experiência prática, aliada a significativa produção teórica nas áreas em jogo.
German literature, Germanic languages. Scandinavian languages
We present Lang-n-Send, a pi-calculus that is equipped with language definitions. Processes can define languages in operational semantics, and use them to execute programs. Furthermore, processes can send and receive pieces of operational semantics through channels. We present a reduction semantics for Lang-n-Send, and we offer examples that demonstrate some of the scenarios that Lang-n-Send captures.
Giovanna D'Agostino, Davide Martincigh, Alberto Policriti
Given an order of the underlying alphabet we can lift it to the states of a finite deterministic automaton: to compare states we use the order of the strings reaching them. When the order on strings is the co-lexicographic one \emph{and} this order turns out to be total, the DFA is called Wheeler. This recently introduced class of automata -- the \emph{Wheeler automata} -- constitute an important data-structure for languages, since it allows the design and implementation of a very efficient tool-set of storage mechanisms for the transition function, supporting a large variety of substring queries. In this context it is natural to consider the class of regular languages accepted by Wheeler automata, i.e. the Wheeler languages. An inspiring result in this area is the following: it has been shown that, as opposed to the general case, the classic determinization by powerset construction is \emph{polynomial} on Wheeler automata. As a consequence, most classical problems, when considered on this class of automata, turn out to be "easy" -- that is, solvable in polynomial time. In this paper we consider computational problems related to Wheelerness, but starting from non-deterministic automata. We also consider the case of \emph{reduced} non-deterministic ones -- a class of NFA where recognizing Wheelerness is still polynomial, as for DFA's. Our collection of results shows that moving towards non-determinism is, in most cases, a dangerous path leading quickly to intractability. Moreover, we start a study of "state complexity" related to Wheeler DFA and languages, proving that the classic construction for the intersection of languages turns out to be computationally simpler on Wheeler DFA than in the general case. We also provide a construction for the minimum Wheeler DFA recognizing a given Wheeler language.
We continue the research on the generative capacity of contextual grammars where contexts are adjoined around whole words (externally) or around subwords (internally) which belong to special regular selection languages. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We investigate contextual grammars with strictly locally testable selection languages and compare those families to families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages.
Using the premises of literary intermediality theory, the paper dwells on the particular performability of a literary text, in which a concert is not only described but also played out as a distinct socially significant phenomenon of contemporary culture. It is because of the performative dimension, which is an essential medium between actual musical events and their verbal rendition, between the embodiment of music in movements, gestures, sounds of instruments, program pieces, and its presentation in interpretations that are historically determined and motivated by personal poetologies of authors, that such texts could be treated as texts-concerts. It is stated that a literary text-concert thematizes and describes a concert event using specific names of musical pieces and their performers, drawing attention to the performing style and individual manner of expression used by musicians as well as the sound of musical instruments while interpreting specific musical compositions. The text itself is conceptualized as a concert, i.e., the plot may be framed by a concert event or be presented as a special concert event with a detailed description of the conditions of the performance (acoustic space, the drama, timing, atmosphere, acoustic background, relevant auditory habits, and performative and ritualistic elements of the concert) and their impact on the listener. Due to particular structural technologies aimed at the most adequate and vocal rendering of the musical performance, a text of this type is played out as a concert that exceeds the limits of representation and displays such dimensions as embodiment, mediality, or eventfulness. In a metaphorical sense, the text is a stage on which the musical performance plays out, which is often combined with the discourse on the author’s creative becoming. Since a text-concert is constituted through intermedial links with music, it has the potential of revealing its own mediality, showing the things it talks about, and in such a way transcending the limits of its content. The analysis is based on Julio Cortazar’s essay Around the Piano with Thelonius Monk and Friedrich Christian Delius’s The Future of Beauty.
German literature, Germanic languages. Scandinavian languages
We consider a language together with the subword relation, the cover relation, and regular predicates. For such structures, we consider the extension of first-order logic by threshold- and modulo-counting quantifiers. Depending on the language, the used predicates, and the fragment of the logic, we determine four new combinations that yield decidable theories. These results extend earlier ones where only the language of all words without the cover relation and fragments of first-order logic were considered.
We study the language inclusion problem $L_1 \subseteq L_2$ where $L_1$ is regular or context-free. Our approach relies on abstract interpretation and checks whether an overapproximating abstraction of $L_1$, obtained by overapproximating the Kleene iterates of its least fixpoint characterization, is included in $L_2$. We show that a language inclusion problem is decidable whenever this overapproximating abstraction satisfies a completeness condition (i.e., its loss of precision causes no false alarm) and prevents infinite ascending chains (i.e., it guarantees termination of least fixpoint computations). This overapproximating abstraction of languages can be defined using quasiorder relations on words, where the abstraction gives the language of all the words "greater than or equal to" a given input word for that quasiorder. We put forward a range of such quasiorders that allow us to systematically design decision procedures for different language inclusion problems such as regular languages into regular languages or into trace sets of one-counter nets, and context-free languages into regular languages. In the case of inclusion between regular languages, some of the induced inclusion checking procedures correspond to well-known state-of-the-art algorithms like the so-called antichain algorithms. Finally, we provide an equivalent language inclusion checking algorithm based on a greatest fixpoint computation that relies on quotients of languages and, to the best of our knowledge, was not previously known.
Probabilistic programming is the idea of writing models from statistics and machine learning using program notations and reasoning about these models using generic inference engines. Recently its combination with deep learning has been explored intensely, leading to the development of deep probabilistic programming languages such as Pyro. At the core of this development lie inference engines based on stochastic variational inference algorithms. When asked to find information about the posterior distribution of a model written in such a language, these algorithms convert this posterior-inference query into an optimisation problem and solve it approximately by gradient ascent. In this paper, we analyse one of the most fundamental and versatile variational inference algorithms, called score estimator, using tools from denotational semantics and program analysis. We formally express what this algorithm does on models denoted by programs, and expose implicit assumptions made by the algorithm. The violation of these assumptions may lead to an undefined optimisation objective or the loss of convergence guarantee of the optimisation process. We then describe rules for proving these assumptions, which can be automated by static program analyses. Some of our rules use nontrivial facts from continuous mathematics, and let us replace requirements about integrals in the assumptions, by conditions involving differentiation or boundedness, which are much easier to prove automatically. Following our general methodology, we have developed a static program analysis for Pyro that aims at discharging the assumption about what we call model-guide support match. Applied to the eight representative model-guide pairs from the Pyro webpage, our analysis finds a bug in one of these cases, reveals a non-standard use of an inference engine in another, and shows the assumptions are met in the remaining cases.
The aim of this article is to analyse the construction of learners’ discoursive images by mapping the summaries presented in textbooks of German as a Foreign Language (ALE). Therefore, we aim to investigate how these constructions anticipate the kind of insertion that this learner would have / could occupy in this community of production / circulation of texts in the target language. Seen in these terms, the theoretical framework is constructed from the articulation between the polyphonic perspective of language (BAKHTIN, 2011), the notion of discursive practices (FOUCAULT, 2004, MAINGUENEAU, 2008), the disciplining of knowledge (FOUCAULT, 2002) and the relevance of such articulation for a critique of Applied Linguistics from Rocha and Daher (2015). Through the analysis of German as a foreign language textbooks, we observe the construction of a learner image that seems to draw him/her out of situations of interaction, considering him/her as a spectator, who will be responsible for repeating sentences and structures determined by an artificial simulation of communicative situations, rather than allowing him/her spaces of interaction and insertion in these situations. In addition, the materials communicate an image of a learner-consumer-tourist, interested in learning German to make trips, a reality that is distant from the majority of Brazilian learners.
German literature, Germanic languages. Scandinavian languages