In the context of an IP network, we investigate an interesting case of the inverse shortest path problem using the concept of network centrality. For a given network, the centrality distribution associated with the links of a network can be determined based on the number of shortest paths passing through each link. An entropy measure for this distribution is defined, and we then forumulate the inverse shortest problem in terms of maximizing this entropy. We then obtain a centrality distribution that is as broadly distributed as possible subject to the topology constraints. An appropriate change in the weight of a link alters the number of shortest paths that pass through it, thereby modifying the centrality distribution. The idea is to obtain a centrality distribution that maximizes the entropy. This problem is shown to be NP-hard, and a heuristic approach is proposed. An application to handling link failure scenarios in Open Shortest Path First routing is discussed.

We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated.

Contextual grammars are introduced by Solomon Marcus in 1969 based on the fundamental concept of descriptive linguistics of insertion of strings in given contexts. Internal contextual grammars are introduced by Păun and Nguyen in 1980. For contextual grammars several descriptional complexity measures and levels of ambiguity have been defined. In this paper, we analyze the trade-off between ambiguity and complexity of languages generated by internal contextual grammars. The notion of a pseudo inherently ambiguous language with respect to two complexity measures is introduced and investigated. These languages can be generated by unambiguous grammars which are minimal with respect to one measure and ambiguous if they are minimal with respect to the other measure. An open problem from [15] is solved in this framework.

Self-assembly is a process in which simple objects autonomously combine themselves into larger objects. It is considered as a promising technique in nano-technology. In this paper, we propose a graph-based self-assembly model. Two simple graphsG1andG2with a vertex of common degree overlap and a new self-assembled graph is formed. Besides studying the properties of these self assembled graphs, we answer the question: can a given set of graphs be generated through the process of self-assembly? If so, how to find the generator that could generate the given set of graphs by the process of self-assembly. The question of the existence of the minimal generator is also discussed. The necessary and sufficient condition for a graphHto be obtained by the iterated self-assembly of the graphGis also answered. We also conclude that the problem of finding the generator is decidable.

Grammatical Inference is the technique by which a grammar that best describes a given set of input samples is inferred. This paper considers the inference of tree grammars from a set of sample input trees. Inference of grammars for fixed arity trees is well studied, in this paper we extend the method to give algorithms for inference of grammars for variable arity trees. We give algorithms for inference of local, single type and regular grammar and also consider the use of negative samples. The variable arity trees we consider can be used for representation of XML documents and the algorithms we have given can be used for validation as well as for schema inference.

In this paper we consider hexagonal arrays on triangular grids and introduce hexagonal local picture languages and hexagonal tiling systems defining hexagonal recognizable picture languages, motivated by an analogous study of rectangular arrays by Giammarresi and Restivo. We also introduce hexagonal Wang tiles to define hexagonal Wang systems (HWS) as a formalism to describe hexagonal picture languages. It is noticed that the family of hexagonal picture languages defined by hexagonal Wang systems and the family recognized by hexagonal tiling systems coincide. Analogous to hv-domino systems describing rectangular arrays, we define xyz-domino systems and prove that recognizable hexagonal picture languages are characterized as projections of xyz-local picture languages.

In this paper, we initially consider representation of 2D black–white images and 3D objects using finite state automata. We describe transformation of scaling on the 2D image by an operation on the FSA. We also give constructions for getting the projections of a 3D object on to coordinate planes and for reconstructing the 3D object from its projections. We define minimization of nondeterministic FSAs and give an O(e 2 ) (e is the number of edges in the FSA) algorithm for minimization of NFAs. Later, we define a WFA and describe various properties of WFA. We define four normal forms of WFA and show how a WFA can be normalized into any of these forms. We show the equivalence of WFAs with ∊ edges and ∊-free WFAs. Then, we define minimization of WFAs and present an algorithm to minimize a WFA.

Systolic pyramid automata accepting square arrays are defined. Homogeneous and semi-homogeneous pyramid automata are shown to have equal power though regular pyramid automata are more powerful. Languages accepted by these automata are compared with languages generated by array grammars and languages accepted by one-way 2-D cellular automata. Hexagonal pyramid automata are also considered and are shown to accept some languages generated by hexagonal array grammars.