International Journal of Foundations of Computer Science

For each alphabet Σ_n = {a₁,a₂,…,a_n}, linearly ordered by a₁ < a₂ < ⋯ < a_n, let C_n be the language of circular or cyclic shifts over Σ_n, i.e., C_n = {a₁a₂ ⋯ a_n-1a_n, a₂a₃ ⋯ a_na₁,…,a_na₁ ⋯ a_n-2a_n-1}. We study a few families of context-free grammars G_n (n ≥1) in Greibach normal form such that G_n generates C_n. The members of these grammar families are investigated with respect to the following descriptional complexity measures: the number of nonterminals ν(n), the number of rules π(n) and the number of leftmost derivations δ(n) of G_n. As in the case of Chomsky normal form, these ν, π and δ are functions bounded by low-degree polynomials. However, the question whether there exists a family of grammars that is minimal w. r. t. all these measures remains open.

Random context picture grammars (rcpgs) are a method of syntactic picture generation. The productions of such a grammar are context-free, but their application is regulated—permitted or forbidden—by context randomly distributed in the developing picture. In previous work we studied three natural subclasses of rcpgs, namely context-free picture grammars (cfpgs), random permitting context picture grammars (rPcpgs) and random forbidding context picture grammars (rFcpgs). We now introduce the notion of table-driven context-free picture grammars (Tcfpgs), and compare them to the above subclasses. We show that Tcfpgs are more powerful than cfpgs, and that they can generate a picture set (more commonly known as a gallery) that rPcpgs cannot. We present two conditions necessary for a gallery to be generated by a Tcfpg, and use these results to find two galleries that cannot be made by any Tcfpg. The second of these galleries can be generated by an rFcpg. Since it is easily shown that any gallery generated by a Tcfpg can be generated by an rFcpg, we can conclude that Tcfpgs are strictly weaker than rFcpgs.

Soliton automata are a mathematical model for certain proposed molecular switching devices. We investigate the closure properties of the class of languages accepted by soliton automata.

As is well known, simple word equations can be very tedious to solve, often requiring specific ad hoc methods. We illustrate this by giving an example of an equation over four unknowns, having only periodic solutions, but for which showing this is not at all obvious.

This paper considers an intra-molecular version of template-guided recombination (TGR), which has been studied in recent papers as an inter-molecular operation. We demonstrate that the intra-molecular TGR operations are distinct from previous intramolecular models for ciliate gene assembly, including the ld and hi operations. We examine the language-theoretic properties of intra-molecular TGR, including closure properties and solutions to language equations.

We define the notion of links, thus generalizing the chain-code, turtle geometry, and collage formalisms. As links can be concatenated, link grammars can be defined in a similar way as chain-code grammars. Context-free link grammars are shown to be strictly more powerful than both context-free chain-code grammars and context-free collage grammars. Moreover, we study the generalization obtained by extending the formalism with the brackets known from the turtle geometry.

Extending the notion of context-free languages and equational sets, we use the approximation theory to define boolean subsets and boolean fuzzy subsets of an algebra. We establish some basic properties of boolean fuzzy sets.

We generalise the well-known notion of programmed grammars without appearance checking by introducing a buffer that could store sequences of rules, thus not necessarily describing the rule to be selected in the very next step, but rather in some future time.

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if no multiset of rules containing a rule from each set of rules assigned to the membranes is applicable anymore, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for (catalytic) P systems and antiport P systems working in different derivation modes.

Membrane systems with carriers holding only a single passenger are known to be computationally complete, although this result does not bound the number of membranes and the number of carriers. We show that actually two membranes suffice.

In this paper finite state recognizers are considered as unary tree recognizers with unary operational symbols. We introduce translation recognizers of a tree recognizer, which are finite state recognizers whose operations are the elementary translations of the underlying algebra of the considered tree recognizer. In terms of translation recognizers we give general conditions under which a class of recognizable tree languages with a given property can be determined by a class of monoids determining the class of string languages having the same property.

We look at spiking neural P systems (SN P systems, for short) all of whose neurons are bounded. We show that a language L ⊆ (0 + 1)* is regular if and only if 1L (i. e., with a supplementary prefix of 1) is generated by a bounded SN P system. This result does not hold when the prefix is replaced by a suffix. For example, 0*1 cannot be generated by a bounded SN P system.

Soliton automata are a mathematical model for molecular switching devices. For even the simple case of soliton automata based on trees the behaviour is not known. For example, only two examples of such soliton automata were known the transition monoid of which is not the symmetric group on the set of states; and in these cases the transition monoid is the corresponding alternating group.

We establish new bounds on the number of states of a tree-based soliton automaton and a sufficient condition for when the transition monoid of such a soliton automaton consists only of even permutations of the set of states. We also summarize the results of a systematic enumeration of tree-based soliton automata by which additional exceptions were found, each an alternating group in its natural representation.

We introduce a new type of finite copying parallel rewriting system, i. e., grammars with linked nonterminals, which extend the generative capacity of context-free grammars. They can be thought of as having sentential forms where some instances of a nonterminal may be linked. The context-free-like productions replace a nonterminal together with its connected instances. New links are only established between symbols of the derived subforms. A natural limitation is to bound the degree of synchronous rewriting. We present an infinite degree hierarchy of separated language families with the property that degree one characterizes the family of regular and degree two the family of context-free languages. Furthermore, the hierarchy is a refinement of the known hierarchy of finite copying rewriting systems. Several closure properties known from equivalent systems are summarized.

A uniform mathematical description of quantum automata as quantum finite automata, quantum linear bounded automata, and quantum Turing machines is introduced, and the existence of such automata under certain circumstances is investigated. Such quantum automata are modelled by isometric rather than unitary operators, reflecting the fact that computation is primarily irreversible in contrast to physical phenomena in the microworld. The global conditions determine the local conditions of the operators.

We investigate the intersection of Church-Rosser languages and (strongly) context-free languages. The intersection is still a proper superset of the deterministic context-free languages as well as of their reversals, while its membership problem is solvable in linear time. For the problem whether a given Church-Rosser or context-free language belongs to the intersection we show completeness for the second level of the arithmetic hierarchy. The equivalence of Church-Rosser and context-free languages is Π₁-complete. It is proved that all considered intersections are pairwise incomparable. Finally, closure properties under several operations are investigated.

A pumping condition for ultralinear languages is proved. Some examples are given using that condition to state lower bounds on the rank of some ultralinear languages and to prove that a certain language is not ultralinear. The restriction to the metalinear case is also investigated.

A generalization of centralized and returning parallel communicating grammar systems with linear components (linear CPC grammar systems) is studied. It is known that linear CPC grammar systems are more powerful than regular CPC grammar systems and that CPC grammar systems with context-free components are more powerful than linear CPC grammar systems. Here, the intermediate model of metalinear CPC grammar systems is studied. This is a CPC grammar system where the master is allowed to use metalinear rules whereas the remaining components are restricted to use linear rules only. It turns out that metalinear CPC grammar systems are more powerful than linear CPC grammar systems and less powerful than CPC grammar systems with context-free components. Furthermore, it is shown that all languages generated by metalinear CPC grammar systems are semilinear.

This work is a continuation of the investigation started in [12], where a new-old type of control on context-free grammars is considered. This type of control is extracted and abstracted from a paper ([2]) with very solid linguistic motivations. The goal of this paper is to complete the picture of path-controlled grammars started in [12] with some mathematical properties which are missing from the aforementioned work: closure and decidability properties, including a polynomial recognition algorithm.

Here we introduce cooperating distributed systems of restarting automata and establish that in mode = 1 they correspond to the non-forgetting restarting automaton.

Restarting automata can be considered as a machine model as well as regulated rewriting systems. We introduce a measure of ambiguity for restarting automata which recognizes a language as a projection of its characteristic language (containing also auxiliary—non-input—symbols) into its input alphabet. Based on this measure we define an ambiguity measure of languages. This measure can be considered as a measure of non-determinism of languages. We show that there is an infinite hierarchy with respect to the degree of ambiguity even inside linear languages and that there are linear languages with a linear ambiguity.

Membrane algorithms with subalgorithms inspired by simulated annealing are treated in this paper. Simulated annealing is inherently a kind of local search but it modifies a solution to a worse one with a probability determined by "temperature". The temperature of simulated annealing is changed according to "cooling schedule". On the other hand, the subalgorithm introduced here has constant temperature which is determined by the region where the subalgorithm is. It is called Brownian subalgorithm since the subalgorithm incorporates "thermal movement" of a solution in the search space but does not simulate "annealing".

Computer simulations show that a membrane algorithm which has three regions and has a Brownian subalgorithm in each region can obtain very good approximate solutions for several benchmark problems of the traveling salesman problem. However, the algorithm, occasionally, gets quite bad solutions (twice as large as the optimum) for a problem. A membrane algorithm which has both Brownian and genetic subalgorithms never gets such a bad solution (only 8% worse than the optimum) for all problems examined, although, in average, it is not as good as the algorithm with Brownian only. The result indicates that membrane algorithm with subalgorithms under different approximate mechanisms may be robust under a wide range of problems.

It was recently found that concatenation of formal languages has a logical dual (A. Okhotin, The dual of concatenation, Theoret. Comput. Sci., 345 (2005), 425–447). In this paper, the closure or nonclosure of common language families under dual concatenation with finite, co-finite and regular languages is determined. In addition, language equations with union, linear concatenation and dual concatenation with co-finite constants are shown to be almost equal in power to linear conjunctive grammars.

We continue the study of the spiking neural P systems considered as transducers of binary strings or binary infinite sequences, and we investigate their ability to compute morphisms. The class of computed morphisms is rather restricted: length preserving or erasing, and the so-called 2-block morphisms can be computed; however, non-erasing non-length-preserving morphisms cannot be computed.

We consider the minimal height of a derivation tree as a complexity measure for context-free languages and show that this leads to a strict and dense hierarchy between logarithmic and linear (arbitrary) tree height. In doing so, we improve a result obtained by Gabarro in [7]. Furthermore, we provide a counter-example to disprove a conjecture of Čulik and Maurer in [6] who suggested that all languages with logarithmic tree height would be regular. As a new method, we use counter-representations where the successor relation can be handled as the complement of context-free languages.

A similar hierarchy is obtained considering the ambiguity as a complexity measure.

We investigate binary words and ω-words, mainly those generated by D0L systems. We compare the numbers of occurrences of ab and ba as (scattered) subwords by introducing a 'difference function'. Of special interest are the 'balanced' or 'fair' words for which the function assumes the value 0. If the three first words in a D0L sequence are fair, so are all words in the sequence. Two kinds of matrices constitute a useful technical tool in the study. An explicit formula, leading to various consequences, is obtained for the difference function.

It is known that the neighborhood of a regular language with respect to an additive distance is regular. We introduce an additive weighted finite automaton model that provides a conceptually simple way to reprove this result. We consider the state complexity of converting additive weighted finite automata to deterministic finite automata. As our main result we establish a tight upper bound for the state complexity of the conversion.

Generalised Łukasiewicz languages are simply described languages having good information-theoretic properties. An especially desirable property is the one of being a prefix code. This paper addresses the question under which conditions a generalised Łukasiewicz language is a prefix code. Moreover, an upper bound on the delay of decipherability of a generalised Łukasiewicz language is derived.

We continue our investigation of the generative power of cooperating distributed grammar systems (CDGSs), using the previously introduced ≤k-, =k-, and ≥k-competence-based cooperation strategies and context-free components that rewrite the sentential form in a parallel manner. This leads to new characterizations of the languages generated by (random context) ET0L systems and recurrent programmed grammars.

In this paper, SC-expressions are developed, based on automata theory, for specifying synchronization constraints in parallel object-oriented languages. The predecessor of SC-expressions, the synchronization expressions, was introduced in the ParC parallel programming language in the early nineties [19]. However, ParC is not an object-oriented language and also a number of basic features of synchronization expressions are inadequate for object-oriented languages. SC-expressions are developed for object-oriented environment. They are different from synchronization expressions in basic ideas and assumptions. Here we describe the basic ideas of SC-expressions and their applications in object-oriented languages. We also study the problem of inheritance of the SC-expressions.