Equal matrix languages and Kleene closure

It is shown that the family of equal matrix languages (EML) which intersects the family of context-sensitive and context-free languages is not closed under Kleene closure, intersection and complementation. The family of bounded EML whose generative power lies between that of bounded context-sensitive languages and bounded context-free languages is shown to be a class of unambiguous languages. Operations that preserve unambiguity and certain decidability questions are discussed.     

Classes of regular and context-free languages over countably infinite alphabets

For a countably infinite alphabet Δ, the classes Reg(Δ) of regular languages and CFL(Δ) of context-free languages over Δ are defined by way of an encoding. All the languages contained in these classes are decidable, and these classes do have many properties in common with the class of regular languages Reg(Σ) and the class of context-free languages CFL(Σ), respectively, where Σ is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over Δ. Finally, the classes Reg(Δ) and CFL (Δ) are compared to the classes of languages over Δ that are defined by Autebert, Beauquier, and Boasson.     

Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

Comparing eye movements during mathematical word problem solving in Chinese and German

Language plays an important role in word problem solving. Accordingly, the language in which a word problem is presented could affect its solution process. In particular, East-Asian, non-alphabetic languages are assumed to provide specific benefits for mathematics compared to Indo-European, alphabetic languages. By analyzing students’ eye movements in a cross-linguistic comparative study, we analyzed word problem solving processes in Chinese and German. 72 German and 67 Taiwanese undergraduate students solved PISA word problems in their own language. Results showed differences in eye movements of students, between the two languages. Moreover, independent cluster analyses revealed three clusters of reading patterns based on eye movements in both languages. Corresponding reading patterns emerged in both languages that were similarly and significantly associated with performance and motivational-affective variables. They explained more variance among students in these variables than between the languages alone. Our analyses show that eye movements of students during reading differ between the two languages, but very similar reading patterns exist in both languages. This result supports the assumption that the language alone is not a sufficient explanation for differences in students’ mathematical achievement, but that reading patterns are more strongly related to performance.     

A comparison of mathematical programming modeling systems

We compare three mathematical programming modeling languages, GAMS, OMNI and MathPro. To understand the properties of these languages, we formulate four linear programs in each language. The formulations are representative of the kinds of model structures one encounters in practice. Each of the languages focuses on a different view of linear programs. GAMS approximates algebra, OMNI uses the activity view and MathPro uses a block schematic. We summarize our experiences with the languages and suggest areas for further enhancement.     

Sur les automates qui reconnaissent une famille de langages

The main results about automatas and the languages they accept are easily extended to automatas which recognize a family of languages (L_i)_iεI of a free monoid, that is to automatas which recognize simultaneously all the languages L_i. This generalization enhances the notion of automata of type (p,r) introduced by S. Eilenberg [4]. In a similar way the notion of syntactic monoid of a family of languages extends the notion of syntactic monoid of a language. This extension is far from being trivial since we show that every finite monoid is the syntactic monoid of a recognizable partition of a free monoid, though this is false for the syntactic monoids of languages.      

On the word problem for syntactic monoids of piecewise testable languages

Piecewise testable languages are widely studied area in the theory of automata. We analyze the algebraic properties of these languages via their syntactic monoids. In this paper a normal form is presented for 2- and 3-piecewise testable languages and a log-asymptotic estimate is given for the number of words over these monoids.     

Semantics of algorithmic languages

This is a survey of methods of formalizing semantics of programming languages (algorithmic languages and specification languages). Principal attention is devoted to the logical approach.Translated from Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Matematicheskaya Statistika, Teoreticheskaya Kibernetika, Vol. 20, pp. 95–166, 1983.     

Disjunctive splittability of languages

Decompositions of languages over a finite alphabetX are investigated. Let T be a class of languages overX satisfying the following condition: (#) T contains at least one dense language, and every dense subset of an element in T is again in T. A language is said to be DT-splittable if it is a disjoint union of infinitely many discrete disjunctive languages in T which are locally finite of rank 1. It is shown that a language is DT-splittable if and only if it is a union of dense languages in T. The class P of all prefix codes satisfies the condition (#). DP-splittability of languages is investigated in detail. A language A is said to besemi-DT-splittable if A\F is DT-splittable for some finite languageF. Semi-DP-splittability is investigated. Semi-DP-splittability of catenations of languages is also studied.     

Growth rates of power-free languages

We propose a new fast algorithm for calculating the growth rate of complexity for regular languages. Based on this algorithm, we develop an efficient universal method for estimating the upper bound of the growth rates for power-free languages. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds, and discover some general regularities.     

Complexity measurement of natural and artificial languages

We compared entropy for texts written in natural languages (English, Spanish) and artificial languages (computer software) based on a simple expression for the entropy as a function of message length and specific word diversity. Code text written in artificial languages showed higher entropy than text of similar length expressed in natural languages. Spanish texts exhibit more symbolic diversity than English ones. Results showed that algorithms based on complexity measures differentiate artificial from natural languages, and that text analysis based on complexity measures allows the unveiling of important aspects of their nature. We propose specific expressions to examine entropy related aspects of tests and estimate the values of entropy, emergence, self‐organization, and complexity based on specific diversity and message length. © 2014 Wiley Periodicals, Inc. Complexity 20: 25–48, 2015     

From finitary to infinitary second‐order logic

A back and forth condition on interpretations for those second‐order languages without functional variables whose non‐logical vocabulary is finite and excludes functional constants is presented. It is shown that this condition is necessary and sufficient for the interpretations to be equivalent in the language. When applied to second‐order languages with an infinite non‐logical vocabulary, excluding functional constants, the back and forth condition is sufficient but not necessary. It is shown that there is a class of infinitary second‐order languages whose non‐logical vocabulary is infinite for which the back and forth condition is both necessary and sufficient. It is also shown that some applications of the back and forth construction for second‐order languages can be extended to the infinitary second‐order languages. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the integration of data and mathematical modeling languages

This paper examines ways in which the addition of data modeling features can enhance the capabilities of mathematical modeling languages. It demonstrates how such integration is achieved as an application of the embedded languages technique proposed by Bhargava and Kimbrough [4]. Decision-making, and decision support systems, require the representation and manipulation of both data and mathematical models. Several data modeling languages as well as several mathematical modeling languages exist, but they have different sets of these capabilities. We motivate with a detailed example the need for the integration of these capabilities. We describe the benefits that might result, and claim that this could lead to a significant improvement in the functionality of model management systems. Then we present our approach for the integration of these languages, and specify how the claimed benefits can be realized.The author's work on this paper was performed in conjunction with research funded by the Naval Postgraduate School.     

On possible growths of Toeplitz languages

We consider a new family of factorial languages whose subword complexity grows as Φ(n ^α ), where α is the only positive root of some transcendental equation. The asymptotic growth of the complexity function of these languages is studied by discrete and analytical methods, a corollary of the Wiener-Pitt theorem inclusive. The factorial languages considered are also languages of arithmetical factors of infinite words; so, we describe a new family of infinite words with an unusual growth of arithmetical complexity.     

Preface

The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L∩R) where h is a morphism, R is a regular language and L is the maximal solution of an equation $\text{?(X) = g(X)}$, where ? is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.     

Fuzzy ontology representation using OWL 2

The need to deal with vague information in Semantic Web languages is rising in importance and, thus, calls for a standard way to represent such information. We may address this issue by either extending current Semantic Web languages to cope with vagueness, or by providing a procedure to represent such information within current standard languages and tools. In this work, we follow the latter approach, by identifying the syntactic differences that a fuzzy ontology language has to cope with, and by proposing a concrete methodology to represent fuzzy ontologies using OWL 2 annotation properties. We also report on some prototypical implementations: a plug-in to edit fuzzy ontologies using OWL 2 annotations and some parsers that translate fuzzy ontologies represented using our methodology into the languages supported by some reasoners.     

EOL and ETOL array languages

In this paper we study the families of ETOL and EOL array languages. Standard forms for ETOL and EOL array systems are defined and closure properties of the families are studied. Relations of these families with other developmental array languages and other array languages are studied.     

Rationality for subclasses of 321-avoiding permutations

We prove that every proper subclass of the 321-avoiding permutations that is defined either by only finitely many additional restrictions or is well-quasi-ordered has a rational generating function. To do so we show that any such class is in bijective correspondence with a regular language. The proof makes significant use of formal languages and of a host of encodings, including a new mapping called the panel encoding that maps languages over the infinite alphabet of positive integers avoiding certain subwords to languages over finite alphabets.     

Automaticity of semigroups of regular languages

It is proved that there exist semigroups of regular languages not possessing automatic structure of a certain special form and also that semigroups of regular languages over a one-letter alphabet are automatic.     

Monoides pointes

We introduce here objects which appear naturally in the study of the syntactic monoids of non rational languages: the pairs consisting of a monoid together with a distinguished subset. Elementary properties of syntactic monoids are derived from theorems of universal algebra on the objects. Monoids with a distinguished subset define an equivalence relationship on formal languages: the classes of rational and context-free languages are considered with respect to this equivalence relationship. Eilenberg's theorem of varieties is expressed within this framework.