Homomorphic characterizations of recursively enumerable languages with very small language classes

In this paper, we attempt to characterize the class of recursively enumerable languages with much smaller language classes than that of linear languages. Language classes, and , of (i,j) linear languages and (i,j) minimal linear languages are defined by posing restrictions on the form of production rules and the number of nonterminals. Then the homomorphic characterizations of the class of recursively enumerable languages are obtained using these classes and a class, , of minimal linear languages. That is, for any recursively enumerable language L over Σ, an alphabet Δ, a homomorphism h : Δ^*→Σ^* and two languages L₁ and L₂ over Δ in some classes mentioned above can be found such that L = h(L₁∩L₂). The membership relations of L₁ and L₂ of the main results are as follows:(I) For posing restrictions on the forms of production rules, the following result is obtained:(1) and .This result is the best one and cannot be improved using . However, with posing more restriction on L₂, this result can be improved and the follwing statement is obtained.(2) and .(II) For posing restrictions on the numbers of nonterminals, the follwing result is obtained.(3) and .We believe this result is also the best.     

A note on the recursive enumerability of some classes of recursively enumerable languages

An elementary proof is presented for the fact that the class of infinite recursive languages is not recursively enumerable. Its relevance for contemporary linguistics and computer science is explained.     

Scattered context grammars generate any recursively enumerable language with two nonterminals

By showing that two nonterminals are sufficient, we present the optimal lower bound on the number of nonterminals of scattered context grammars being able to generate any recursively enumerable language.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

On sets polynomially enumerable by iteration

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ^p_1si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are ^p_1si-self-reducible are bi-enumerable. We also show that when the ^p_1si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.     

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.     

On locally reversible languages

There exist several works that study the class of reversible languages defined as the union closure of 0-reversible languages, their properties and suitable representations. In this work we define and study the class of locally reversible languages, defined as the union closure of $k$-reversible languages. We characterize the class and prove that it is a local (positive) variety of formal languages. We also extend the definition of quasi-reversible automata to deal with locally reversible languages and propose a polynomial algorithm to obtain, for any given locally $k$-reversible language, a quasi-$k$-reversible automaton.     

On OCL-based imperative languages

The Object Constraint Language (OCL) is a well-accepted ingredient in model-driven engineering and accompanying modeling languages such as UML (Unified Modeling Language) and EMF (Eclipse Modeling Framework) that support object-oriented software development. Among various possibilities, OCL offers the formulation of class invariants and operation contracts in form of pre- and postconditions, and side-effect free query operations. Much research has been done on OCL and various mature implementations are available for it. OCL is also used as the foundation for several modeling-specific programming and transformation languages. However, an intrusive way of embedding OCL into these language hampers us when we want to benefit from the existing achievements for OCL. In response to this shortcoming, we propose the language SOIL (Simple OCL-like Imperative Language), which we implemented in the UML and OCL modeling tool USE to amend its declarative model validation features. The expression sub-language of SOIL is identical to OCL. SOIL adds imperative constructs for programming in the domain of models. Thus by employing OCL and SOIL, it is possible to describe any operation in a declarative way and in an operational way on the modeling level without going into the details of a conventional programming language. In contrast to other similar approaches, the embedding of OCL into SOIL is done in a careful, non-intrusive way so that purity of OCL is preserved.     

On case-based learnability of languages

Case-based reasoning is deemed an important technology to alleviate the bottleneck of knowledge acquisition in Artificial Intelligence (AI). In case-based reasoning, knowledge is represented in the form of particular cases with an appropriate similarity measure rather than any form of rules. The case-based reasoning paradigm adopts the view that an Al system is dynamically changing during its life-cycle which immediately leads to learning considerations. Within the present paper, we investigate the problem of case-based learning of indexable classes of formal languages. Prior to learning considerations, we study the problem of case-based representability and show that every indexable class is case-based representable with respect to a fixed similarity measure. Next, we investigate several models of case-based learning and systematically analyze their strengths as well as their limitations. Finally, the general approach to case-based learnability of indexable classes of formal languages is prototypically applied to so-called containmet decision lists, since they seem particularly tailored to case-based knowledge processing.     

On characterizations of preinvex fuzzy mappings

Several characterizations about preinvex fuzzy mapping are obtained in this paper. Firstly, an equivalent condition of preinvex fuzzy mapping is established under certain conditions. Furthermore, the necessary and sufficient conditions for differentiable and twice differentiable preinvex fuzzy mapping are provided by using the given equivalent condition of preinvex fuzzy mapping. Finally, a new proof of some known important conclusions is offered. These results generalize and improve some known results.     

On languages of automaton counter machines

A class of formal languages (ACML) acceptable by automaton counter machines is considered. This class is shown to be close with respect to the operations of union, regular intersection, concatenation, infinite iteration, homomorphism, and inverse homomorphism. It follows from here that this class is a full abstract family of languages [7] with all the properties following from this. Furthermore, the ACML is close with respect to intersection and substitution but is not closed with respect to complement and reverse. For the ACML class, the problems of emptiness and recognition of words of a language given by an automaton counter machine are decidable, but the problems of inclusion and equivalence of languages are undecidable. A comparison with other classes of languages (regular, context-free, context-sensitive, and Petri-net languages) is performed.