Linear automata are automata with two reading heads starting from the two extremes of the input, are equivalent to 5' -> 3' Watson-Crick (WK) finite automata. The heads read the input in opposite directions and the computation finishes when the heads meet. These automata accept the class LIN of linear languages. The deterministic counterpart of these models, on the one hand, is less expressive, as only a proper subset of LIN, the class 2detLIN is accepted; and on the other hand, they are also equivalent in the sense of the class of the accepted languages. Now, based on these automata models, we characterize the class of 2detLIN languages with a Myhill-Nerode type of equivalence classes. However, as these automata may do the computation of both the prefix and the suffix of the input, we use prefix-suffix pairs in our classes. Additionally, it is proven that finitely many classes in the characterization match with the 2detLIN languages, but we have some constraints on the used prefix-suffix pairs, i.e., the characterization should have the property to be complete and it must not have any crossing pairs.
Jan Baumeister, Arthur Correnson, Bernd Finkbeiner
et al.
Stream-based runtime monitors are safety assurance tools that check at runtime whether the system's behavior satisfies a formal specification. Specifications consist of stream equations, which relate input streams, containing sensor readings and other incoming information, to output streams, representing filtered and aggregated data. This paper presents a framework for the stream-based specification language RTLola. We introduce a new intermediate representation for stream-based languages, the StreamIR, which, like the specification language, operates on streams of unbounded length; while the stream equations are replaced by imperative programs. We developed a set of optimizations based on static analysis of the specification and have implemented an interpreter and a compiler for several target languages. In our evaluation, we measure the performance of several real-world case studies. The results show that using the StreamIR framework reduces the runtime significantly compared to the existing StreamIR interpreter. We evaluate the effect of the optimizations and show that significant performance gains are possible beyond the optimizations of the target language's compiler. While our current implementation is limited to RTLola, the StreamIR is designed to accommodate other stream-based languages, enabling their interpretation and compilation into all available target languages.
Backreference is a well-known practical extension of regular expressions and most modern programming languages, such as Java, Python, JavaScript and more, support regular expressions with backreferences (rewb) in their standard libraries for string processing. A difficulty of backreference is non-regularity: unlike some other extensions, backreference strictly enhances the expressive power of regular expressions and thus rewbs can describe non-regular (in fact, even non-context-free) languages. In this paper, we investigate the expressive power of rewbs by comparing rewbs to multiple context-free languages (MCFL) and parallel multiple context-free languages (PMCFL). First, we prove that the language class of rewbs is a proper subclass of unary-PMCFLs. The class of unary-PMCFLs coincides with that of EDT0L languages, and our result strictly improves the known upper bound of rewbs. Additionally, we show that, however, the language class of rewbs is not contained in that of MCFLs even when restricted to rewbs with only one capturing group and no captured references. Therefore, in general, the parallelism seems essential for rewbs. Backed by these results, we define a novel syntactic condition on rewbs that we call closed-star and observe that it provides an upper bound on the number of times a rewb references the same captured string. The closed-star condition allows dispensing with the parallelism: that is, we prove that the language class of closed-star rewbs falls inside the class of unary-MCFLs, which is equivalent to that of EDT0L systems of finite index. Furthermore, as additional evidence for the robustness of the condition, we show that the language class of closed-star rewbs also falls inside the class of nonerasing stack languages (NESL).
O artigo tem por objetivo discutir os processos de reflexão e conscientização sobre categorias didáticas do planejamento de aula, que ocorreram no âmbito da disciplina “Atividades de Estágio: Alemão” na Universidade de São Paulo no segundo semestre de 2019. Nesse sentido, apresentar-se-ão primeiro algumas noções teóricas sobre modelos e funções do estágio na formação docente no Brasil e na Alemanha, além de um panorama das principais mudanças que ocorreram, nos últimos vinte anos, nas resoluções do Conselho Nacional de Educação concernentes às atividades de estágio nos cursos brasileiros de licenciatura. Na sequência, a análise dos dados empíricos focalizará os processos de conscientização que ocorreram no grupo de licenciandas investigado, no que diz respeito à sua percepção sobre a variedade de objetivos possíveis no ensino de alemão, bem como às funções didáticas de diferentes fases de uma aula, com ênfase na fase inicial. Algumas reflexões sobre a importância da mentoria na formação inicial de professoras concluirão este estudo.
German literature, Germanic languages. Scandinavian languages
System programming languages are typically compiled in a linear pipeline process, which is a completely opaque and isolated to end-users. This limits the possibilities of performing meta-programming in the same language and environment, and the extensibility of the compiler itself by end-users. We propose a novel redefinition of the compilation process in terms of interpreting the program definition as a script. This evaluation is performed in an environment where the full compilation pipeline is implemented and exposed to the user via a meta-object protocol, which forms the basis for a meta-circular definition and implementation of the programming language itself. We demonstrate the feasibility of this approach by bootstrapping a self-compiling implementation of Sysmel, a static and dynamic typed Smalltalk and C++ inspired programming language.
In this paper, we focus on the problem of dynamically analysing concurrent software against high-level temporal specifications. Existing techniques for runtime monitoring against such specifications are primarily designed for sequential software and remain inadequate in the presence of concurrency -- violations may be observed only in intricate thread interleavings, requiring many re-runs of the underlying software. Towards this, we study the problem of predictive runtime monitoring, inspired by the analogous problem of predictive data race detection studied extensively recently. The predictive runtime monitoring question asks, given an execution $σ$, if it can be soundly reordered to expose violations of a specification. In this paper, we focus on specifications that are given in regular languages. Our notion of reorderings is trace equivalence, where an execution is considered a reordering of another if it can be obtained from the latter by successively commuting adjacent independent actions. We first show that the problem of predictive admits a super-linear lower bound of $O(n^α)$, where $n$ is the number of events in the execution, and $α$ is a parameter describing the degree of commutativity. As a result, predictive runtime monitoring even in this setting is unlikely to be efficiently solvable. Towards this, we identify a sub-class of regular languages, called pattern languages (and their extension generalized pattern languages). Pattern languages can naturally express specific ordering of some number of (labelled) events, and have been inspired by popular empirical hypotheses, the `small bug depth' hypothesis. More importantly, we show that for pattern (and generalized pattern) languages, the predictive monitoring problem can be solved using a constant-space streaming linear-time algorithm.
This is the proceedings of the Sixth International Workshop on Languages for Modelling Variability (MODEVAR 2024) which was held at Bern, Switzerland, February 06th 2024.
The survey provides an overview of the work done in the last 10 years to characterise solutions to equations in groups in terms of formal languages. We begin with the work of Ciobanu, Diekert and Elder, who showed that solutions to systems of equations in free groups in terms of reduced words are expressible as EDT0L languages. We provide a sketch of their algorithm, and describe how the free group results extend to hyperbolic groups. The characterisation of solutions as EDT0L languages is very robust, and many group constructions preserve this, as shown by Levine. The most recent progress in the area has been made for groups without negative curvature, such as virtually abelian, the integral Heisenberg group, or the soluble Baumslag-Solitar groups, where the approaches to describing the solutions are different from the negative curvature groups. In virtually abelian groups the solutions sets are in fact rational, and one can obtain them as $m$-regular sets. In the Heisenberg group producing the solutions to a single equation reduces to understanding the solutions to quadratic Diophantine equations and uses number theoretic techniques. In the Baumslag-Solitar groups the methods are combinatorial, and focus on the interplay of normal forms to solve particular classes of equations. In conclusion, EDT0L languages give an effective and simple combinatorial characterisation of sets of seemingly high complexity in many important classes of groups.
Extraction from relative clauses is generally taken to be unacceptable in Icelandic, unlike in the Mainland Scandinavian languages. Recent studies on Mainland Scandinavian show that the type of dependency as well as the embedding predicate matters for the acceptability of such extractions, and the study of spontaneously produced examples has improved our ability to create felicitous extraction contexts. The studies of Icelandic extraction predate these findings, and there is to date no study which systematically compares parallel sentences in Icelandic and Mainland Scandinavian. This article presents such a study, using two acceptability judgment experiments, one in Icelandic and one in Swedish, drawing on newly gained insights about fronting conditions in the two languages to create plausible contexts. The Icelandic participants rated extraction from relative clauses as unnatural, with a very large acceptability cost compared to in situ versions and good fillers. Extraction from að-clauses received mixed ratings, and local fronting was rated on a par with the in situ versions. In Swedish, extraction from relative clauses was rated as natural a majority of the time. There was no extraction cost in local fronting, extraction from att-clauses, or extraction from relative clauses in existential sentences, while extraction with other embedding predicates incurred some cost. No differences relating to the embedding predicate were seen in Icelandic. The study corroborates the view that extraction from relative clauses is unacceptable in Icelandic.
Es herrscht in der Forschung Einigkeit darüber, dass beim Debunking (Falschinformation erkennen und enttarnen) von Fake News nachträgliches Fact-Checking zwar notwendig, aber oft unzureichend ist. Die Praxis zeigt, dass Fake News wesentlich höhere Reichweiten erzielen als deren Richtigstellungen. Sie sind oft so formuliert, dass sie Empörung auslösen und ein bestimmtes Weltbild bestätigen, was unter Nutzergruppen in Echokammern ihre Verbreitungswahrscheinlichkeit wesentlich erhöht. Mit einer Nachricht, dass etwas falsch ist, einen Nachrichtwert zu erzielen, der eine erfolgreiche Verbreitung der Richtigstellung gewährleistet, bleibt eine Herausforderung. Dieser Beitrag geht auf die Notwendigkeit ein, neue Narrative beim Debunking zu entwickeln, die sich von der Vorstellung verabschieden, bei der Richtigstellung Nachrichtenwert generieren zu müssen. Er hebt die entscheidende Rolle der Förderung von Medienkritikfähigkeit im Umgang mit Fake News im Deutschunterricht hervor und schlägt ein Narrativ der Information über Desinformation vor, das nicht nur geprüfte Fakten, sondern auch die kollektiven Stimmungen der Gesellschaft thematisiert.
Abstract (english): Fake News and the News Value of (Mis-)information. About the Necessity of New Narratives for Debunking.
In research on fake news, it is acknowledged that fact-checking for debunking and corrective messages quickly fade from memory. Even if they are necessary, they are often insufficient for countering misinformation. Practice has shown that fake news generates high news value through emotional messages and extends its range quicker than corrective messages. The greater emotionality of misinformation increases the belief in fake news and decreases truth discernment. It remains a challenge to release corrective messages which are able to generate higher news values. This contribution deals with the necessity to develop new narratives for debunking, which give up the focus on news value. It puts into focus the important role of media literacy and critique skills in countering misinformation in German classes and suggests a new narrative for information about misinformation which thematizes both the role of verified facts and the role of collective moods.
A description of language design choices that have profound effects on software quality, criticism of how ordinary OO languages address them, and explanation of the thinking behind Eiffel's corresponding mechanisms.
Martin Ruefenacht, Derek Schafer, Anthony Skjellum
et al.
Over the past two decades, C++ has been adopted as a major HPC language (displacing C to a large extent, andFortran to some degree as well). Idiomatic C++ is clearly how C++ is being used nowadays. But, MPIs syntax and semantics defined and extended with C and Fortran interfaces that align with the capabilities and limitations of C89 and Fortran-77.Unfortunately, the language-independent specification also clearly reflects the intersection of what these languages could syntactically and semantically manage at the outset in 1993, rather than being truly language neutral.In this paper, we propose a modern C++ language interface to replace the C language binding for C++ programmers with an upward-compatible architecture that leverages all the benefits of C++11-20 for performance, productivity, and interoperability with other popular C++ libraries and interfaces for HPC. Demand is demonstrably strong for this second attempt at language support for C++ in MPI after the original interface, which was added in MPI-2, then was found to lack specific benefits over theC binding, and so was subsequently removed in MPI-3. Since C++ and its idiomatic usage have evolved since the original C++ language binding was removed from the standard, this new effort is both timely and important for MPI applications. Also, many C++ application programmers create their own, ad hoc shim libraries over MPI to provide some degree of abstraction unique to their particular project, which means many such abstraction libraries are being devised without any specific commonality other than the demand for such.
We show that it is decidable whether two regular languages of infinite trees are separable by a deterministic language, resp., a game language. We consider two variants of separability, depending on whether the set of priorities of the separator is fixed, or not. In each case, we show that separability can be decided in EXPTIME, and that separating automata of exponential size suffice. We obtain our results by reducing to infinite duration games with ω-regular winning conditions and applying the finite-memory determinacy theorem of Büchi and Landweber.
In this thesis we use quasiorders on words to offer a new perspective on two well-studied problems from Formal Language Theory: deciding language inclusion and manipulating the finite automata representations of regular languages. First, we present a generic quasiorder-based framework that, when instantiated with different quasiorders, yields different algorithms (some of them new) for deciding language inclusion. We then instantiate this framework to devise an efficient algorithm for searching with regular expressions on grammar-compressed text. Finally, we define a framework of quasiorder-based automata constructions to offer a new perspective on residual automata.
Psycholinguistic research has long established that focus-marked words have a processing advantage over other words in an utterance, e.g., they are recognized more quickly and remembered better. More recently, studies have shown that listeners infer contextual alternatives to a focused word in a spoken utterance, when marked with a contrastive accent, even when the alternatives are not explicitly mentioned in the discourse. This has been shown by strengthened priming of contextual alternatives to the word, but not other non-contrastive semantic associates, when it is contrastively accented, e.g., after hearing “The customer opened the window," salesman is strongly primed, but not product. This is consistent with Rooth's (1992) theory that focus-marking signals the presence of alternatives to the focus. However, almost all of the research carried out in this area has been on Germanic languages. Further, most of this work has looked only at one kind of focus-marking, by contrastive accenting (prosody). This paper reports on a cross-modal lexical priming study in Mandarin Chinese, looking at whether focus-marking heightens activation, i.e., priming, of words and their alternatives. Two kinds of focus-marking were investigated: prosodic and syntactic. Prosodic prominence is an important means of focus-marking in Chinese, however, it is realized through pitch range expansion, rather than accenting. The results showed that focused words, as well as their alternatives, were primed when the subject prime word carried contrastive prosodic prominence. Syntactic focus-marking, however, did not enhance priming of focused words or their alternatives. Non-contrastive semantic associates were not primed with either kind of focus-marking. These results extend previous findings on focus and alternative priming for the first time to Chinese. They also suggest that the processing advantages of focus, including priming alternatives, are particularly related to prosodic prominence, at least in Chinese and Germanic languages. This research sheds light on what linguistic mechanisms listeners use to identify important information, generate alternatives, and understand implicature necessary for successful communication.