On the subword complexity of locally catenative dol languages

The subword complexity of language K, denoted Gv;_K, is the function of positive integers such that Gv;_K(n) equals the number of subwords of length n that occur in (words of) K. It is proved that if K is a locally catenative DOL language, then Gv;_K is bounded by a linear function.     

On the efficient construction of quasi-reversible automata for reversible languages

Quasi-reversible automata is a suitable representation for reversible languages. In this work a method is proposed to obtain such an automaton for any given reversible language represented by its minimal DFA. Our method runs in polynomial time respect to the size of the minimal DFA and improves a previous exponential method. Previous bound for the size of quasi-reversible automata is also reduced.     

Inference of reversible tree languages

In this paper, we study the notion of k-reversibility and k-testability when regular tree languages are involved. We present an inference algorithm for learning a k-testable tree language that runs in polynomial time with respect to the size of the sample used. We also study the tree language classes in relation to other well known ones, and some properties of these languages are proven.     

On a class of languages recognizable by probabilistic reversible decide-and-halt automata

We analyze the properties of probabilistic reversible decide-and-halt automata (DH-PRA) and show that there is a strong relationship between DH-PRA and 1-way quantum automata. We show that a general class of regular languages is not recognizable by DH-PRA by proving that two “forbidden” constructions in minimal deterministic automata correspond to languages not recognizable by DH-PRA. The shown class is identical to a class known to be not recognizable by 1-way quantum automata. We also prove that the class of languages recognizable by DH-PRA is not closed under union and other non-trivial Boolean operations.     

Parsing with probabilistic strictly locally testable tree languages

Probabilistic k-testable models (usually known as k-gram models in the case of strings) can be easily identified from samples and allow for smoothing techniques to deal with unseen events during pattern classification. In this paper, we introduce the family of stochastic k-testable tree languages and describe how these models can approximate any stochastic rational tree language. The model is applied to the task of learning a probabilistic k-testable model from a sample of parsed sentences. In particular, a parser for a natural language grammar that incorporates smoothing is shown.     

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 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.     

Stack and locally finite transformations on structures with reversible transitions

Cybernetics and Systems Analysis - Theorems 1–3 provide a unified and, in a certain sense, universal approach for the translation of recursions into iterative backtracking form and also for...     

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 depth in EDTOL languages

Languages of the form L₁={aⁿ:n?1}, L₂={(abⁿ)^m: n,m?1}, L₃={(a(bcⁿ) ^m)^k: n,m,k?1}, etc. differ in what may be called ‘depth’. It turns out that this depth is closely related to the structure of finite state automata associated with EDTOL systems generating these languages. For a given system the corresponding automaton is defined, and the relevant characteristics of its structure are examined.     

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.