Operational state complexity of nested word automata

We introduce techniques to prove lower bounds for the number of states needed by finite automata operating on nested words. We study the state complexity of Boolean operations and obtain lower bounds that are tight within an additive constant. The results for union and complementation differ from corresponding bounds for ordinary finite automata. For reversal and concatenation, we establish lower bounds that are of a different order than the worst-case bounds for ordinary finite automata.     

On the complexity of computing the profinite closure of a rational language

Profinite topology is used in the classification of rational languages. In particular, several important decidability problems, related to the Malcev product, reduce to the computation of the closure of a rational language in the profinite topology. It is known that, given a rational language by a deterministic automaton, computing a deterministic automaton accepting its profinite closure can be done with an exponential upper bound. This paper is dedicated the study of a lower bound for this problem: we prove that, in some cases, if the alphabet contains at least three letters, it requires an exponential time.     

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.     

Detecting patterns in finite regular and context-free languages

We consider some natural variations on the following classic pattern-matching problem: given an NFA M over the alphabet Σ and a pattern p over some alphabet Δ, does there exist a word x∈L(M) such that x matches p? We consider the restricted problem where M only accepts a finite language. We also consider the variation where only some factor of x is required to match the pattern p. We show that both of these problems are NP-complete. We also consider the same problems for context-free grammars; in this case the problems become PSPACE-complete.     

On the subword complexity of m-free D0L languages

A word is called m-free (m ? 2) if it does not contain a subword of the form x^m where x is a nonempty word. A language is called m-free if it consists of m-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which to each positive integer n assigns the number of different subwords of length n occuring in words of K. It is known that if a D0L language K is m-free for some m ? 2, then, for all n, π_K(n) ? qn log₂n for some positive integer q. We demonstrate that there exists a 3-free D0L language K on three letters such that, for all n ? n₀, π_K(n) ? rn log₂n for some positive real r and a positive integer n₀. We also demonstrate that if m ? 3 and K is an m-free D0L language on two letters, then, for all n, π_K(n) ? pn for some positive integer p.     

Estimation of state complexity of combined operations

It appears that the state complexity of each combined operation has its own special features. Thus, it is important and practical to obtain good estimates for some commonly used general cases. In this paper, we consider the state complexity of combined Boolean operations and give an exact bound for all of them in the case when the alphabet is not fixed. Moreover, we show that for any fixed alphabet, this bound can be reached in infinitely many cases. We also consider the state complexity of multiple catenations. The state complexities are obtained in the cases of the catenations of three and four languages. An estimate for the catenation of an arbitrary number of languages is given, which is very close to the state complexities in the three and four languages cases.     

正则语言的一个特征

Myhill-Nerode定理利用等价关系描述了正则语言的一个重要特征,它是有限自动机理论中的一个经典、优美的结果。为了将Myhill-Nerode定理推广到更一般的情形,引入了有限自动机M上的状态转移半群和Σ*上的M-半群,讨论了其若干性质。在此基础上,将Myhill-Nerode定理中的等价关系一般化,给出了正则语言的一个新的特征定理,Myhill-Nerode定理成为该定理的一个推论。讨论了正则语言的最一般的特征,提出了有待进一步研究的问题。     

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.     

Unconstrained optimal control of regular languages

This paper formulates an unconstrained optimal policy for control of regular languages realized as deterministic finite state automata (DFSA). A signed real measure quantifies the behavior of controlled sublanguages based on a state transition cost matrix and a characteristic vector as reported in an earlier publication. The state-based optimal control policy is obtained by selectively disabling controllable events to maximize the measure of the controlled plant language without any further constraints. Synthesis of the optimal control policy requires at most n iterations, where n is the number of states of the DFSA model. Each iteration solves a set of n simultaneous linear algebraic equations. As such, computational complexity of the control synthesis is polynomial in n.     

On the complexity of the instance checking problem in concept languages with existential quantification

Most of the work regarding complexity results for concept languages consider subsumption as the prototypical inference. However, when concept languages are used for building knowledge bases including assertions on individuals, the basic deductive service of the knowledge base is the so-called instance checking, which is the problem of checking if an individual is an instance of a given concept. We consider a particular concept language, calledALE, and we address the question of whether instance checking can be really solved by means of subsumption algorithms in this language. Therefore, we indirectly ask whether considering subsumption as the prototypical inference is justified. Our analysis, carried out considering two different measure of complexity, shows that inALE instance checking is strictly harder than subsumption. This result singles out a new source of complexity in concept languages, which does not show up when checking subsumption between concepts.This work has been supported by the ESPRIT Basic Research Action N.6810-COMPULOG 2 and by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the CNR (Italian Research Council).     

Inference of finite-state transducers from regular languages

Finite-state transducers are models that are being used in different areas of pattern recognition and computational linguistics. One of these areas is machine translation, where the approaches that are based on building models automatically from training examples are becoming more and more attractive. Finite-state transducers are very adequate to be used in constrained tasks where training samples of pairs of sentences are available. A technique to infer finite-state transducers is proposed in this work. This technique is based on formal relations between finite-state transducers and finite-state grammars. Given a training corpus of input-output pairs of sentences, the proposed approach uses statistical alignment methods to produce a set of conventional strings from which a stochastic finite-state grammar is inferred. This grammar is finally transformed into a resulting finite-state transducer. The proposed methods are assessed through series of machine translation experiments within the framework of the EUTRANS project.     

Efficient enumeration of words in regular languages

The cross-section enumeration problem is to list all words of length n$n$ in a regular language L$L$ in lexicographical order. The enumeration problem is to list the first m$m$ words in L$L$ according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in n+t$n+t$, where t$t$ is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable.     

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.