On the ratio of growth functions in EDTOL languages

EDTOL systems can be used to approximate real numbers by considering the limit of the ratio of the number of occurences of one symbol to the number of occurences of another symbol in a sequence of derived words of increasing length. The complexity of this limit value is shown to be related to the structure of the generating system.     

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 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 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 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 non-determinism in machines and languages

Non-deterministic computation is not really computation, but the difference with real computation is blurred. We study in detail various levels of non-determinism in computations on non-deterministic Turing machines with polynomial bounds on the resources. Meanwhile, we consider numerous query languages, implicit logic, choice logic, order invariant logic, and restrictions of second-order logic, and establish correspondences between all these formalisms for both deterministic and non-deterministic queries. To the degrees of non-determinism in the computations, correspond levels of non-determinism in the logical definitions. Our main contribution is to characterize various complexity classes between PTIME and PSPACE, by several logical means, thus translating open questions in complexity theory to open questions in logic related to the use of the non-determinism.     

On measuring nondeterminism in regular languages

It is well known that allowing nondeterminism in a finite automaton can produce in the most extreme case an exponential savings in the number of states required to recognize a regular language. This paper studies situations intermediate between forbidding nondeterminism and allowing it. The amount of nondeterminism used by a finite automaton is quantified, so that the decrease in the size of the state space that occurs as the amount of nondeterminism that is permitted increases in increments can be studied. These intermediate situations are shown always to lie between two extremes:(1) there are no savings as the amount of nondeterminism increases incrementally, so that savings occur only when the amount of nondeterminism becomes unlimited;(2) each increment of nondeterminism results in additional savings, the number s of states decreasing approximately as s^1/i, until exponential savings have been achieved after about i = logs/log log s increments.     

On possibility qualification in natural languages

The theory of possibility, recently introduced by L. A. Zadeh, is explored in the particular subject of possibility-qualified propositions as a basis for approximate reasoning. The concept of ε-possibility related to fuzzy sets has a formulation that verifies some criteria of minimal uncertainty. It is shown how to derive possibility-qualified propositions from the classical translation rules in fuzzy logic.     

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 expressing metonymic relations in multiple languages

Recently, the scientific interest in addressing metonymy phenomena from a computational perspective has increased significantly. Considerable effort is invested in this, but issues addressing metonymy in the context of natural language generation have been widely ignored so far, and also comparable multilingual analyses are rather sparse. Motivated by these shortcomings, we investigate methods for representing knowledge required to express metonymic relations in several ways and in multiple languages, and we present techniques for generating these alternative verbalizations. In particular, we demonstrate how mapping schemata that enable lexical expressions on the basis of conceptual specifications to be built are derived from the Qualia Structure of Pustejovsky's Generative Lexicon. Moreover, our enterprise has led to the exposition of interesting cross-language differences, notably the use of prefixed verbs and compound nouns in German, as opposed to widely equivalent expressions entailing implicit metonymic relations, as frequently found in English. A main achievement of our approach lies in bringing computational lexical semantics and natural language generation closer together, so that the linguistic foundations of lexical choice in natural language generation are strengthened.     

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.     

On regular drawn symbolic picture languages

Drawn symbolic pictures are an extension of drawn pictures obtained by associating a symbol from an alphabet to each point of the picture. In the paper we will address some new interesting issues derived from the introduction of the symbols and we will identify the conditions, which ensure the preservation of properties holding for drawn pictures in the setting of the proposed extension.     

On characterizations of recursively enumerable languages

Summary Geffert has shown that earch recursively enumerable languageL over can be expressed in the formL{h(x) ^–1 g(x)x in ⁺} ^* where is an alphabet andg, h is a pair of morphisms. Our purpose is to give a simple proof for Geffert's result and then sharpen it into the form where both of the morphisms are nonerasing. In our method we modify constructions used in a representation of recursively enumerable languages in terms of equality sets and in a characterization of simple transducers in terms of morphisms. As direct consequences, we get the undecidability of the Post correspondence problem and various representations ofL. For instance,L =(L ₀) ^* whereL ₀ is a minimal linear language and is the Dyck reductiona, A.