A CKY parser for picture grammars

We study the complexity of the membership or parsing problem for pictures generated by a family of picture grammars: Siromoney's Context-Free Kolam Array grammars (coincident with Matz's context-free picture grammars). We describe a new parsing algorithm, which extends the Cocke, Kasami and Younger's classical parsing technique for string languages and preserves the polynomial time complexity.     

Rectangular polyomino set weak (1, 2)-achievement games

In a polyomino set (1, 2)-achievement game the maker and the breaker alternately mark one and two previously unmarked cells respectively. The maker’s goal is to mark a set of cells congruent to one of a given set of polyominoes. The breaker tries to prevent the maker from achieving his goal. The teams of polyominoes for which the maker has a winning strategy is determined up to size 4. In set achievement games, it is natural to study infinitely large polyominoes. This enables the construction of super winners that characterize all winning teams up to a certain size.     

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.     

Kernel methods for learning languages

This paper studies a novel paradigm for learning formal languages from positive and negative examples which consists of mapping strings to an appropriate high-dimensional feature space and learning a separating hyperplane in that space. Such mappings can often be represented flexibly with string kernels, with the additional benefit of computational efficiency. The paradigm inspected can thus be viewed as that of using kernel methods for learning languages.     

Solutions to four open problems concerning controlled pure grammar systems

In this paper, we address several open problems concerning pure grammar systems (pGSs) and their controlled versions. More specifically, we prove the following four results. (I) Regular-controlled pGSs having a single component define the family of regular languages. (II) pGSs having two components controlled by infinite regular languages define the family of recursively enumerable languages. (III) Regular-controlled pGSs without any erasing rules define the family of regular languages not containing the empty string. (IV) pGSs define a proper subfamily of the family of regular languages.     

(DNA) computing by carving

 Inspired by the experiments reported recently in the emerging area of DNA computing, we consider a somewhat unusual type of a computation strategy: generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. We call this a computation by carving. This leads both to a speculation with possible important consequences and to interesting theoretical computer science (formal language) questions. The speculation is that in this way we can “compute” non-recursively enumerable languages, because the family of recursively enumerable languages is not closed under complementation. The formal language theory questions concern sequences of languages with certain regularities, needed as languages to be extracted from the total language of candidate solutions of a problem. Specifically, we consider sequences of languages obtained by starting from a given regular language and iteratively applying to it a given finite state sequential transducer (a gsm). Computing by carving with respect to such a sequence of languages can identify all context-sensitive languages and can also lead to non-recursively enumerable languages (but not all recursively enumerable languages can be obtained in this way). In practical circumstances, the carving process should be finite, hence, in general, approximations of the desired language are obtained. We also briefly discuss this aspect.     

A mean string algorithm to compute the average among a set of 2D shapes

An algorithm to compute the mean shape, when the shape is represented by a string, is presented as a modification of the well-known string edit algorithm. Given N strings of symbols, a string edit sequence defines a mapping between their corresponding symbols. We transform these sets of mapped symbols (edges) into piecewise linear functions and we compute their mean. To transform them into functions, we use the equation of the line defining their edges, and the percentage of their length, in order to have a common parameterization. The algorithm has been experimentally tested in the computation of a representative among a class of shapes in a clustering procedure in the domain of a graphics recognition application.     

Mutation systems

We propose mutation systems as a model of the evolution of a string subject to the effects of mutations and a fitness function. One fundamental question about such a system is whether knowing the rules for mutations and fitness, we can predict whether it is possible for one string to evolve into another. To explore this issue, we define a specific kind of mutation system with point mutations and a fitness function based on conserved strongly k-testable string patterns. We show that for any k greater than 1, such systems can simulate computation by both finite state machines (FSMs) and asynchronous cellular automata. The cellular automaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyse the efficiency of the FSM simulation assuming random point mutations.     

Matching typed and untyped realizability

Realizability interpretations of logics are given by saying what it means for computational objects of some kind to realize logical formulae. The computational objects in question might be drawn from an untyped universe of computation, such as a partial combinatory algebra, or they might be typed objects such as terms of a PCF-style programming language. In some instances, one can show that a particular untyped realizability interpretation matches a particular typed one, in the sense that they give the same set of realizable formulae. In this case, we have a very good fit indeed between the typed language and the untyped realizability model — we refer to this condition as (constructive) logical full abstraction.We give some examples of this situation for a variety of extensions of PCF. Of particular interest are some models that are logically fully abstract for typed languages including non-functional features. Our results establish connections between what is computable in various programming languages and what is true inside various realizability toposes. We consider some examples of logical formulae to illustrate these ideas, in particular their application to exact real-number computability.     

Termination Proofs for String Rewriting Systems via Inverse Match-Bounds

Annotating a letter by a number, one can record information about its history during a rewrite derivation. In each rewrite step, numbers in the reduct are updated depending on the redex numbering. A string rewriting system is called match-bounded if there is a global upper bound to these numbers. Match-boundedness is known to be a strong sufficient criterion for both termination and preservation of regular languages. We show that the string rewriting systems whose inverse (left and right hand sides exchanged) is match-bounded, also have exceptional properties, but slightly different ones. Inverse match-bounded systems need not terminate; they effectively preserve context-free languages; their sets of normalizable strings and their sets of immortal strings are effectively regular. These languages can be used to decide the normalization, the uniform normalization, the termination and the uniform termination problem for inverse match-bounded systems. We also prove that the termination problem is decidable in linear time, and that a certain strong reachability problem is decidable, thereby solving two open problems of McNaughton’s. Like match-bounds, inverse match-bounds entail linear derivational complexity on the set of terminating strings.     

On string languages generated by spiking neural P systems with exhaustive use of rules

We continue the study of (extended) spiking neural P systems with exhaustive use of rules by considering these computing devices as language generators. Specifically, a step is associated with a symbol according to the number of spikes emitted by the output neuron and the sequence of these symbols associated with a halting computation constitutes a string. Two cases are considered: one of them interprets a step when no spike is emitted as a specified symbol, the other interprets such a step as the empty string. In both cases, it is proved that finite and recursively enumerable languages are characterized by extended spiking neural P systems working in the exhaustive mode. The relationships with regular languages are also investigated.

On iterated hairpin completion

(Bounded) hairpin completion and its iterated versions are operations on formal languages which have been inspired by hairpin formation in DNA biochemistry. The paper answers two questions asked in the literature about iterated hairpin completion.The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion.In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular: actually, it is not context-free, but context-sensitive.     

Improving workflow modularity using a concern-specific layer on top of Unify

Workflows are a popular means of automating processes in many domains, ranging from high-level business process modeling to lower-level web service orchestration. However, state-of-the-art workflow languages offer a limited set of modularization mechanisms. This results in monolithic workflow specifications, in which different concerns are scattered across the workflow and tangled with one another. This hinders the design, evolution, and reusability of workflows expressed in these languages. We address this problem through the Unify framework. This framework enables uniform modularization of workflows by supporting the specification of all workflow concerns – including crosscutting ones – in isolation of each other. These independently specified workflow concerns are connected to each other using workflow-specific connectors. In order to further facilitate the development of workflows, we enable the definition of concern-specific languages (CSLs) on top of the Unify framework. A CSL facilitates the expression of a family of workflow concerns by offering abstractions that map well to the concerns' domain. Thus, domain experts can add concerns to a workflow using concern-specific language constructs. We exemplify the specification of a workflow in Unify, and show the definition and application of two concern-specific languages built on top of Unify.     

Regular Tree Languages as an Abstract Domain in Program Specialisation

On-line partial evaluation algorithms include a generalisation step, which is needed to ensure termination. In partial evaluation of logic and functional programs, the usual generalisation operation is the most specific generalisation (msg) of expressions. This can cause loss of information, which is especially serious in programs whose computations first build some internal data structure that is then used to control a subsequent phase of execution—a common pattern of computation. If the size of the intermediate data is unbounded at partial evaluation time then the msg will lose almost all information about its structure. Hence subsequent phases of computation cannot be effectively specialised.In this paper the problem is tackled by introducing regular tree languages into a partial evaluation algorithm. A regular tree language is a set of terms defined by tree automata or tree grammars. In the algorithm, regular tree approximations of sets of terms encountered during partial evaluation are constructed. The critical point is that when generalisation is performed, the upper bound on regular tree languages can be combined with the msg, thus preserving recursive information about term structure. This approach also allows the specialisation of programs with respect to goals whose arguments range over regular tree languages.The algorithm is presented as an instance of Leuschel's framework for abstract specialisation of logic programs. This provides a generic algorithm parameterised by an abstract domain—regular trees in this case. The correctness requirements from his framework are established. The extension of the algorithm to propagate regular approximations of answers as well as calls is also presented, increasing the amount of specialisation that can be obtained. Finally a technique for increasing precision based on wrapper functions is introduced.     

A comparison study of polyominoes explorations in a physical and virtual manipulative environment

This study develops virtual manipulative, polyominoes kits for junior high school students to explore polyominoes. The current work conducts a non‐equivalent group pretest–post‐test quasi‐experimental design to compare the performance difference between using physical manipulatives and virtual manipulatives in finding the number of polyominoes. Sixty eighth‐grade students from two different classes in a junior high school in Taipei County of Taiwan participated in this study. The current research randomly selected one class as the experiment group and the other as the control group. Students in the experiment group used virtual manipulatives to explore polyominoes and those in the control group used physical manipulatives. The results revealed that learning in the experiment group is as effective as that in the control group. This study identifies two obvious strategies (add one and reduce) among students in both groups. New ideas, including using new symbols to record the results and considering the influence of symmetry and rotation on the figures, occurred in the virtual manipulative group. Students in the virtual environment paid much more attention to exploring the polyomino problem.     

一种特洛伊木马的检测算法

运用字母集合到数字集合的映射理论、字符串的可计算性理论与数论理论，设计了一种特洛伊木马的检测算法，该算法能够有效地检测出特洛伊木马，同已有的检测算法相比，速度较快，不但适合字母文字的可执行程序检测，也适合可能出现的非字母文字所编写的可执行程序的特洛伊木马检测．     

Iconic indexing by 2-d strings

In this paper, we describe a new way of representing a symbolic picture by a two-dimensional string. A picture query can also be specified as a 2-D string. The problem of pictorial information retrieval then becomes a problem of 2-D subsequence matching. We present algorithms for encoding a symbolic picture into its 2-D string representation, reconstructing a picture from its 2-D string representation, and matching a 2-D string with another 2-D string. We also prove the necessary and sufficient conditions to characterize ambiguous pictures for reduced 2-D strings as well as normal 2-D strings. This approach thus allows an efficient and natural way to construct iconic indexes for pictures.     

Sticky-free and overhang-free DNA languages

An essential step of any DNA computation is encoding the input data on single or double DNA strands. Due to the biochemical properties of DNA, complementary single strands can bind to one another forming double-stranded DNA. Consequently, data-encoding DNA strands can sometimes interact in undesirable ways when used in computations. It is crucial thus to analyze properties that guard against such phenomena and study sets of sequences that ensure that no unwanted bindings occur during any computation. This paper formalizes and investigates properties of DNA languages that guarantee their robusteness during computations. After defining and investigating several types of DNA languages possessing good encoding properties, such as sticky-free and overhang-free languages, we give algorithms for deciding whether regular DNA languages are invariant under bio-operations. We also give a method for constructing DNA languages that, in addition to being invariant and sticky-free, possess error-detecting properties. Finally, we present the results of running tests that check whether several known gene languages (the set of genes of a given organism) as well as the input DNA languages used in Adlemans DNA computing experiment, have the defined properties.Received: 6 February 2003, Published online: 2 September 2003Research partially supported by Grants R2824A01 and R220259 of the Natural Sciences and Engineering Research Council of Canada.     

On the language equivalence of NE star-patterns

A pattern is a finite string of constant and variable symbols. The language generated by a pattern is the set of all strings of constant symbols which can be obtained from the pattern by substituting (non-empty) strings for variables. The pattern languages are one of language family which is orthogonal to the Chomsky-type languages hierarchy. They have many applications, such as the extended regular expressions, for instance, in languages Perl, awk, etc. They are well applicable in machine learning as well. There are erasing and non-erasing patterns are used. For non-erasing pattern languages the equivalence of languages is decidable but the inclusion problem for them is undecidable. In extended regular expressions one can use union, concatenation and Kleene star to make more complex patterns. It is also known, that the equivalence problem of extended regular expressions is undecidable. However, the problem, whether the equivalence is decidable for patterns using only concatenation and star still open. In this paper there are some interesting results about inclusion properties and equivalences of some kinds of erasing and non-erasing pattern languages. We show that the equivalence problem of non-erasing patterns in some cases can be reduced to the decidability problem of some very special inclusion properties. These results may be useful to decide whether the language equivalence of non-erasing star-patterns is decidable or not.