Simple chain grammars and languages

A subclass of the LR(0)-grammars, the class of simple chain grammars is introduced. Although there exist simple chain grammars which are not LL(k) for any k>0, this new class of grammars is very closely related to the LL(1) and simple LL(1) grammars. In fact it can be shown that every simple chain grammar has an equivalent simple LL(1) grammar.Cover properties for simple chain grammars are investigated and a deterministic pushdown transducer which acts as a right parser for simple chain grammars is presented.     

Solutions of equations in languages

A context-free grammar corresponds to a system of equations in languages. The language generated by the grammar is the smallest solution of the system. We give a necessary and sufficient condition for an arbitrary solution to be the smallest one. We revive an old criterion to decide that a grammar has a unique solution. All this fits in an approach to search for a grammar for an arbitrary language that is given by other means. The approach is illustrated by the derivation of a grammar for a certain set of bit strings. The approach is used to give an elegant derivation of the grammar for a language accepted by a pushdown automaton.     

State complexity of some operations on binary regular languages

We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.     

A note on equations for commutative regular languages

In this note we prove that the equations satisfied by one-letter regular languages are exactly those satisfied by commutative regular languages. This answers a problem raised by Arto Salomaa.     

Simple context-free languages and free monadic recursion schemes

A context-free language is said to be simple if it is accepted by a single-state deterministic pushdown store acceptor that operates in real-time and accepts by empty store. While the problem remains open of deciding whether or not the language accepted by a deterministic pushdown store acceptor is simple, it is shown that this problem is equivalent to another problem in schemata theory. This question is that of determining whether or not a monadic recursion scheme has a strongly equivalent free scheme.This research was supported in part by the National Science Foundation, Grant No. NSF GJ-803 and DCR74-15091.     

Simple recurrent networks learn context-free and context-sensitive languages by counting

It has been shown that if a recurrent neural network (RNN) learns to process a regular language, one can extract a finite-state machine (FSM) by treating regions of phase-space as FSM states. However, it has also been shown that one can construct an RNN to implement Turing machines by using RNN dynamics as counters. But how does a network learn languages that require counting? Rodriguez, Wiles, and Elman (1999) showed that a simple recurrent network (SRN) can learn to process a simple context-free language (CFL) by counting up and down. This article extends that to show a range of language tasks in which an SRN develops solutions that not only count but also copy and store counting information. In one case, the network stores information like an explicit storage mechanism. In other cases, the network stores information more indirectly in trajectories that are sensitive to slight displacements that depend on context. In this sense, an SRN can learn analog computation as a set of interdependent counters. This demonstrates how SRNs may be an alternative psychological model of language or sequence processing.     

Extension of binary analytical equations to ternary ones

A series of analytical expressions of predicting and representing ternary thermodynamic properties using binary data has been derived by applying the subregular solution model and the Krupkowski equation. The geometrical methods employed for the derivation are the Muggianu-, the Kohler-, the Colinet- and the Toop- methods. The expressions have been used to predict the partial molar excess free energy in the Cd-Pb-Sn system at 760K. The experimental data of the liquid Cd-Pb-Sn solutions are found to be excellently represented by the derived expressions.     

Topologies on formal languages

S. Y. Kuroda has shown that it is possible to attack problems concerning syntactic analysis and translation by means of topological concepts and methods. He presented a way to introduce topologies on context-free languages via the generating grammar, by considering all extensions of nonterminal derivations.We extend Kuroda's concept to the general case of languages and study continuous mappings, compactness and topological connectness. The main tool is an appropriate definition of structural equivalence of grammars and languages, presented with the help of topologies and homeomorphisms. We derive theorems on the topological equivalence of grammars and languages.     

Continuous operations on languages

Most of the operations of interest in language theory arecontinuous in a certain technical sense. For such operations, there always exist infinite sets of languages that areindependent in the sense that no language in such a set can be generated from the other languages in the set by the operations in question.     

A simulation study comparing weighted estimating equations with multiple imputation based estimating equations for longitudinal binary data

Missingness frequently complicates the analysis of longitudinal data. A popular solution for dealing with incomplete longitudinal data is the use of likelihood-based methods, when, for example, linear, generalized linear, or non-linear mixed models are considered, due to their validity under the assumption of missing at random (MAR). Semi-parametric methods such as generalized estimating equations (GEEs) offer another attractive approach but require the assumption of missing completely at random (MCAR). Weighted GEE (WGEE) has been proposed as an elegant way to ensure validity under MAR. Alternatively, multiple imputation (MI) can be used to pre-process incomplete data, after which GEE is applied (MI-GEE). Focusing on incomplete binary repeated measures, both methods are compared using the so-called asymptotic, as well as small-sample, simulations, in a variety of correctly specified as well as incorrectly specified models. In spite of the asymptotic unbiasedness of WGEE, results provide striking evidence that MI-GEE is both less biased and more accurate in the small to moderate sample sizes which typically arise in clinical trials.     

Notes on canonical label languages

Derivations by a phrase-structure grammar may be represented by a word over the set of indices for the rules of the grammar. The set of all label words constitutes the label language for the grammar. The canonical label language is the restriction of the label language to the set of canonical derivations of the grammar. Whether a given language may be the label language for any grammar is partially answered by restricting the question to the canonical derivations for regular and contextfree grammars.     

Simple Bayesian binary framework for discovering significant genes and classifying cancer diagnosis

Given a microarray dataset consisting of two classes, type I and type II, the proposed coherent binary framework sequentially combines a gene-rank algorithm and a classifier. Genes that are expressed at a consistently high level in one type and at a consistently low level in the other type are of much interest. The wider the gap between the expression levels, the more significant the gene is as a discriminator. A new distance metric is used to measure the gap and is obtained using Bayesian nonparametric approaches involving Dirichlet process priors. Significant genes are ranked separately based on the pattern (the genes are over-expressed in type I and under-expressed in type II) or the pattern (the genes are under-expressed in type I and over-expressed in type II). An out-of-sample cross-validation approach is suggested for use in deciding how many significant genes are necessary for the classifier. The classifier uses each selected top-ranked gene to calculate a classification score when a test sample is presented. The sample is then classified as having the type with the larger score. Empirical studies using two public datasets show that top-ranked genes in each pattern clearly distinguish the existing pattern, and the classifier uses a few significant genes to classify the types in the test samples correctly. The framework is a simple, easy alternative to more complex models in terms of its accuracy and robustness.     

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.