Context-free complexity of finite languages

In this paper the investigation of the theory of grammatical complexity as started by Bucher (1981) and Bucher, Culik II, Maurer and Wotschke (1981) is continued. The basic question we are concerned with is the following: Given some finite language L, what is the smallest number of context-free productions needed to generate L, the so-called (context-free) complexity of L. We strengthen some of the results given by Bucher et al. (1981), the main result being a necessary condition for certain sequences of finite languages to be of sublinear complexity.     

The inclusion problem for simple languages

A deterministic pushdown acceptor is called a simple machine when it is restricted to have only one state, operate in real-time, and accept by empty store. While the existence of an effective procedure for deciding equivalence of languages accepted by these simple machines is well-known, it is shown that this family is powerful enough to have an undecidable inclusion problem. It follows that the inclusion problems for the LL(k) languages and the free monadic recursion schemes that do not use an identity function are also undecidable.     

The complexity of graph languages generated by hyperedge replacement

Summary Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.Parts of the results of this paper were presented at 15^th ICALP, [La88b]     

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.     

Growth rates of complexity of power-free languages

We present a new fast algorithm for calculating the growth rate of complexity for regular languages. Using this algorithm we develop a space and time efficient method to approximate growth rates of complexity of arbitrary power-free languages over finite alphabets. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds and discover some general regularities.     

Computational complexity and constraint logic programming languages

We give a complexity analysis of a variety of languages across the spectrum of the CLP scheme. By varying the logic and memory management, the role of the constraints and the role of the logic can be measured. The analysis clarifies the relation between linear/integer programming and constraint logic programming. We also determine how the power of constraints can easily lead to undecidable queries in Datalog languages with constraints. This work is motivated in large part by the problems of efficient implementation of CLP languages and the concomitant need for low level constraint languages.Research partially supported by PSC-CUNY Grant 669287.Research partially supported by NSF Grant IRI-8902511.     

On the subword complexity of square-free DOL languages

The subword complexity of a language K is the function which to every positive integer n assigns the number of different subwords of length n occuring in words of K. A language K is square-free if no word in it contains a subword of the form xx where x is a nonempty word. The (best) upper and lower bounds on the subword complexity of infinite square-free DOL languages are established.     

Remarks on the complexity of nondeterministic counter languages

For classes of languages accepted in polynomial time by multicounter machines, various trade-offs in computing power obtain among the number of counters, the amount of time, and the amount of space required in all cases, deterministic and nondeterministic, on-line and off-line. Hierarchies can be obtained in all cases by varying the number of counters or the amount of time allowed. In the on-line case, nondeterministic counter machines are always more powerful than deterministic counter machines for the same number of counters and the same polynomial time bound. Relationships with open problems are explored.     

On the state complexity of reversals of regular languages

We compare the number of states between minimal deterministic finite automata accepting a regular language and its reversal (mirror image). In the worst case the state complexity of the reversal is 2ⁿ for an n-state language. We present several classes of languages where this maximal blow-up is actually achieved and study the conditions for it. In the case of finite languages the maximal blow-up is not possible but still a surprising variety of different growth types can be exhibited.     

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.     

Measuring the complexity of domain-specific languages developed using MDD

The standard ISO/IEC 25010 (SQuaRE) defines appropriateness as one of the three components of functional suitability, the other two components being completeness and correctness. As users of domain-specific language (DSL) are quite often domain experts with limited programming skills, a DSL might be considered appropriate if the resulting domain-specific programs do not contain an excessive amount of nondomain-related programming elements. This paper describes a metric for measuring the appropriateness of DSLs that are developed using model-driven development (MDD), its evaluation and use. The metric measures the depth of the deepest domain-specific command within abstract syntax trees generated by a DSL. It is aimed at being used during the development of a new DSL and for comparing different DSLs defined over the same domain. It is assumed that during MDD, the metamodel describes the domain-independent part of the DSL, while the model supplies the domain-specific part. This resembles the implementation of DSLs using existing metaprogramming tools that provide off-the-shelf implementations of programming constructs but require manual implementation of the domain-specific language elements.     

State complexity of basic operations on suffix-free regular languages

We investigate the state complexity of basic operations for suffix-free regular languages. The state complexity of an operation for regular languages is the number of states that are necessary and sufficient in the worst-case for the minimal deterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, Kleene star, reversal and the Boolean operations for suffix-free regular languages.     

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.     

Query languages for sequence databases: termination and complexity

This paper develops a query language for sequence databases, such as genome databases and text databases. Unlike relational data, queries over sequential data can easily produce infinite answer sets since the universe of sequences is infinite, even for a finite alphabet. The challenge is to develop query languages that are both highly expressive and finite. This paper develops such a language as a subset of a logic for string databases called Sequence Datalog. The main idea is to use safe recursion to control and limit unsafe recursion. The main results are the definition of a finite form of recursion, called domain-bounded recursion, and a characterization of its complexity and expressive power. Although finite, the resulting class of programs is highly expressive since its data complexity is complete for the elementary functions     

Comparative complexity of the representation of languages by probabilistic automata

We analyze the effect of the degree of isolation of a cut point on the number of states P(U, ) of a probabilistic automaton representing the language U. We give an example of a language Uⁿ consisting of words of length n such that there exist numbers < for which P(Uⁿ, )/P(Uⁿ, )0 as n.Translated from Kibernetika, No. 3, pp. 21–25, May–June, 1989.