Statistical approach to evaluation of internal computer languages

We propose an approach to optimal choice of the tradeoff between the complexity of compiling and interpreting, based on the notion of distance between source, internal, and machine languages. This distance is based on the usage frequency of language constructs and instructions.Translated from Kibernetika, No. 2, pp. 78–80, 85, March–April, 1989.     

Information structure in African languages: corpora and tools

In this paper, we describe tools and resources for the study of African languages developed at the Collaborative Research Centre 632 “Information Structure”. These include deeply annotated data collections of 25 sub-Saharan languages that are described together with their annotation scheme, as well as the corpus tool ANNIS, which provides unified access to a broad variety of annotations created with a range of different tools. With the application of ANNIS to several African data collections, we illustrate its suitability for the purpose of language documentation, distributed access, and the creation of data archives.     

Towards an unrestricted domain TTS system for African tone languages

In this paper we discuss the procedural problems, issues and challenges involved in developing a generic speech synthesizer for African tone languages. We base our development methodology on the “MultiSyn” unit-selection approach, supported by Festival Text-To-Speech (TTS) Toolkit for Ibibio, a Lower Cross subgroup of the (New) Benue-Congo language family widely spoken in the southeastern region of Nigeria. We present in a chronological order, the several levels of infrastructural and linguistic problems as well as challenges identified in the Local Language Speech Technology Initiative (LLSTI) during the development process (from the corpus preparation and refinement stage to the integration and synthesis stage). We provide solutions to most of these challenges and point to possible outlook for further refinement. The evaluation of the initial prototype shows that the synthesis system will be useful to non-literate communities and a wide spectrum of applications.     

Collecting and evaluating speech recognition corpora for 11 South African languages

We describe the Lwazi corpus for automatic speech recognition (ASR), a new telephone speech corpus which contains data from the eleven official languages of South Africa. Because of practical constraints, the amount of speech per language is relatively small compared to major corpora in world languages, and we report on our investigation of the stability of the ASR models derived from the corpus. We also report on phoneme distance measures across languages, and describe initial phone recognisers that were developed using this data. We find that a surprisingly small number of speakers (fewer than 50) and around 10 to 20 h of speech per language are sufficient for the purposes of acceptable phone-based recognition.     

EOL languages are not codings of FPOL languages

One of the useful results concerning EOL languages states that a language is an EOL language if and only if it is a cording of OL language. In this paper we retine this result by demonstrating that there exist EOL languages that are not codings of languages that are generated by propagating OL systems with finite axiom sets. This solves Problem 10 from the L Systems Problem Book '75.     

Relations of flow languages to Petri net languages

A.C. Shaw has introduced the concept of the flow expression which is an extended regular expression and state several results with some conjectures. His conjecture that the flow expressions define context-sensitive languages has been answered negatively by two of the present authors, that is, the flow languages are recursively enumerable.In this paper, it is shown that flow languages for some restricted class of flow expressions are equivalent to Petri net languages. Some related decision problems for flow expressions are also discussed.     

On the intersection of regex languages with regular languages

In this paper we revisit the semantics of extended regular expressions (regex), defined succinctly in the 90s [A.V. Aho, Algorithms for finding patterns in strings, in: Jan van Leeuwen (Ed.), Handbook of Theoretical Computer Science, in: Algorithms and Complexity, vol. A, Elsevier and MIT Press, 1990, pp. 255–300] and rigorously in 2003 by Câmpeanu, Salomaa and Yu [C. Câmpeanu, K. Salomaa, S. Yu, A formal study of practical regular expressions, IJFCS 14 (6) (2003) 1007–1018], when the authors reported an open problem, namely whether regex languages are closed under the intersection with regular languages. We give a positive answer; and for doing so, we propose a new class of machines — regex automata systems (RAS) — which are equivalent to regex. Among others, these machines provide a consistent and convenient method of implementing regex in practice. We also prove, as a consequence of this closure property, that several languages, such as the mirror language, the language of palindromes, and the language of balanced words are not regex languages.     

On nonstochastic languages and homomorphic images of stochastic languages

Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages $\text{{wcw¦w in {a, b}}{}^1\text{}}$ and $\text{{wcw}{}^{\mathrm{R}}\text{¦w in {a, b}}{}^1\text{}}$. Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {a^p¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of_∩ (DUP) = the smallest intersection-closed AFL containing $\text{DUP}\text{= {a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{¦n in N}}$, which is a subfamily of /oK(/oL_Q = the image of the family of rational stochastic languages under nonerasing homomorphisms.     

Image theorems for simple matrix languages andn-parallel languages

Three image theorems are proved for three families of languages in terms of prototype languages and (nondeterministic) generalized sequential machine maps. Further, for one family, then-right linear simple matrix languages of Ibarra, a new characterization theorem is proved.Work carried out under a National Research Council of Canada Grant No. A-7700.     

The equality of EOL languages and codings of ol languages

It is proved that a language is a coding (a letter-to-letter homomorphism) of a OL language, if, and only if, it is an EOL language.     

Rule-based languages

The paper presents a survey of the main formal rule-based languages and semantics. Both procedural (fixpoint) and declarative (model-theoretic) semantics are defined and discussed, including inflationary and noninflationary fixpoint semantics, and the semi-positive, stratified and well-founded semantics. The relative expressive power and com-plexity of the various languages are provided. Nondeterministic rule-based languages are also discussed, and it is shown how nondeterminism can circumvent some difficulties concerning the expressive power of the deterministic languages. Finally, languages with value invention (in the spirit of object-creation in oodbs) are presented and issues of expressive power specific to such languages are discussed.     

Multi-stack-counter languages

A stack-counter acceptor is a stack acceptor in which the storage alphabet is just one letter. The present paper discusses multi-stack-counter acceptors operating in quasirealtime, i.e., acceptors in which each storage tape is a stack counter and in which there are only a bounded number of consecutive-moves. For each positive integerk let be the family of languages accepted byk-stack-counter acceptors (k-counter acceptors). Each is a principal AFL closed under reversal but not under-free substitution or under intersection. Also, and a specific language in each, is exhibited. For each and there are noi andj such that. It is shown that a quasi-real-timek-stackcounter acceptor is equivalent to one operating in non-deterministic real time. Lastly, it is shown that acceptance by final state of ak-stack-counter acceptor is equivalent to acceptance by empty tape and final state.Also formerly with System Development Corporation, Santa Monica, California. Research sponsored in part by the Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-70-C-0023; by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under AFOSR No. F44620-70-C-0013; and by NSF Grant No. GJ454.     

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了de Bruijn有向图语言和Kautz有向图语言的直径。     

Ergodic languages

We present here a new way of defining languages via rewriting systems, and study the obtained families of languages, and their relationship to Chomsky hierarchy.     

Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

Weakly context-sensitive languages as model for programming languages

Summary An abstract family of formal languages containing context-free languages and properly contained in (deterministic) context-sensitive languages is introduced. This family is comprehensive enough to contain e.g. Algol 60 without admitting too complex recursive constructions possible in the frame of general context-sensitive languages.This family is essentially a family of property-languages, whereby the considered properties are restricted to properties which are constructively definable from a finite number of context-free sets.     

Adherences of languages

This paper studies context-free sets of finite and infinite words. In particular, it gives a natural way of associating to a language a set of infinite words. It then becomes possible to begin a study of families of sets of infinite words rather similar to the classical studies of families of languages.     

Insertion languages

The operations of insertion ( ← ) and iterated insertion ( ←₁ ) are simple variants of Kleene's operations · and 1 [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $\text{S}{}^{\mathrm{\leftarrow }}{}^1$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “$\text{S}{}^{\mathrm{\leftarrow }}\text{1 ∩ T}{}^{\mathrm{\leftarrow }}\text{1 = {λ}?}$” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $\text{←}{}_1$, we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “$\text{L = ∑}{}^1\text{?}$” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.