Author name cluster

Mark Daley

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

TCS Journal 2012 Journal Article

Algorithmic decomposition of shuffle on words

Franziska Biegler
Mark Daley
Ian McQuillan

We investigate shuffle-decomposability into two words. We give an algorithm which takes as input a DFA M (under certain conditions) and determines the unique candidate decomposition into words u and v such that L ( M ) = u v if M is shuffle decomposable, in time O ( | u | + | v | ). Even though this algorithm does not determine whether or not the DFA is shuffle decomposable, the sublinear time complexity of only determining the two words under the assumption of decomposability is surprising given the complexity of shuffle, and demonstrates an interesting property of the operation. We also show that for given words u and v and a DFA M we can determine whether u v ⊆ L ( M ) in polynomial time.

Details DOI

TCS Journal 2012 Journal Article

One-reversal counter machines and multihead automata: Revisited

Ehsan Chiniforooshan
Mark Daley
Oscar H. Ibarra
Lila Kari
Shinnosuke Seki

We investigate the power of (1-reversal) counter machines (finite automata with multiple counters, where each counter can “reverse” only once, i. e. , once a counter decrements, it can no longer increment) and one-way multihead finite automata (finite automata with multiple one-way input heads) as a language acceptor. They can be non-deterministic as well as augmented with a pushdown stack. First, we prove that adding a pushdown stack properly strengthens the deterministic counter machines. Non-deterministic counter machines with a pushdown stack are then compared with multihead finite automata. The proof of their incomparability involves an interesting technique: an assumption that a language be accepted by a non-deterministic counter machine would bring a contradictory algorithm to decide an undecidable language. Furthermore, we will show that over bounded languages, these two kinds of machines have the same power, and neither non-determinism nor a pushdown stack makes them stronger.

Details DOI

TCS Journal 2012 Journal Article

Relativized codes

Mark Daley
Helmut Jürgensen
Lila Kari
Kalpana Mahalingam

A code C over an alphabet Σ is a set of words such that every word in C + has a unique factorization over C, that is, a unique C -decoding. When not all words in C + appear as messages, a weaker notion of unique factorization can be used. Thus we consider codes C relative to a given set of messages L, such that each word in L has a unique C -decoding. We extend this idea of relativizing code concepts to restricted message spaces. In general terms, from a predicate P defining a class of codes, P -codes, we derive a relativized version of such codes, P -codes relative to a given language L. In essence, C ⊆ Σ + is a P -code relative to L ⊆ Σ + if P is true on its domain restricted to L. This systematic approach leads to the relativization of the definitions of many classes of codes, including prefix, suffix, bifix and solid codes. It can also be applied to certain classes of languages, like overlap-free languages, which are not codes, but which can be defined using a similar logical framework. In this paper, we explore the mechanism of this relativization and compare it to other existing methods for relativizing code properties to restricted message spaces.

Details DOI

TCS Journal 2009 Journal Article

On the uniqueness of shuffle on words and finite languages

Franziska Biegler
Mark Daley
Markus Holzer
Ian McQuillan

We investigate a special variant of the shuffle decomposition problem for regular languages; namely, when the given regular language is the shuffle of finite languages. The shuffle decomposition into finite languages is, in general, not unique. That is, there are L 1, L 2, L 3, L 4 with but { L 1, L 2 } ≠ { L 3, L 4 }. However, if all four languages are singletons (with at least two combined letters), it follows by a result of Berstel and Boasson [J. Berstel, L. Boasson, Shuffle factorization is unique, Theoretical Computer Science 273 (2002) 47–67] that the solution is unique; that is, { L 1, L 2 } = { L 3, L 4 }. We further show that if L 1 and L 2 are arbitrary finite sets and L 3 and L 4 are singletons (with at least two letters in each), the solution is unique. Therefore, shuffle decomposition of words is unique not only over words, but over arbitrary sets. This is strong as we cannot let all four be arbitrary finite sets. Hopefully, the obtained results will help to better understand the very nature of the shuffle operation.

Details DOI

TCS Journal 2007 Journal Article

On codes defined by bio-operations

Mark Daley
Michael Domaratzki

We consider the classes of ⊕ -codes and ⊗ -codes, which are superclasses of outfix and hyper-codes, respectively. These restrictions are based on the synchronized insertion operation, which serves as a model for the gene rearrangement function in certain unicellular organisms. We investigate the classes of ⊕ -codes and ⊗ -codes from a theoretical perspective, examine their relationships with traditional code classes and consider related decidability problems.

Details DOI

TCS Journal 2007 Journal Article

Regulated RNA rewriting: Modelling RNA editing with guided insertion

Franziska Biegler
Michael J. Burrell
Mark Daley

RNA editing is an important alternative genetic processing event that is known to take place in all higher eukaryotes. We study a model of string rewriting based on the sophisticated RNA editing mechanism found in trypanosome kinetoplasts. We demonstrate basic properties of three principal variants of this model which we show to form a strict hierarchy in terms of expressive power. We also present a method and software for simulating real biological RNA editing via this model and apply the theoretical results to suggest real biological constraints on this process.

Details DOI

TCS Journal 2005 Journal Article

Template-guided DNA recombination

Mark Daley
Ian McQuillan

The family of stichotrichous ciliates have received a great deal of study due to the presence of scrambled genes in their genomes. The mechanism by which these genes are descrambled is of interest both as a biological process and as a model of natural computation. Several formal models of this process have been proposed, the most recent of which involves the recombination of DNA strands based on template guides. We generalize this template-guided DNA recombination model proposed by Prescott, Ehrenfeucht and Rozenberg to an operation on strings and languages. We then proceed to investigate the properties of this operation with the intention of viewing ciliate gene descrambling as a computational process.

Details DOI

TCS Journal 2004 Journal Article

Families of languages defined by ciliate bio-operations

Mark Daley
Lila Kari
Ian McQuillan

We investigate families of languages defined by closure under operations generalized from models of gene descrambling in stichotrichous ciliates. We specifically consider languages that are closed under the synchronized insertion and deletion operations as well as languages closed under the hairpin inversion (hi) operation. Biologically, this studies sets of genes that cannot be further descrambled. In addition, we show that every trio closed under hairpin inversion is also closed under the double loop with alternating direct pointers (dlad)-excision/reinsertion bio-operation.

Details DOI

TCS Journal 2003 Journal Article

Closure and decidability properties of some language classes with respect to ciliate bio-operations

Mark Daley
Oscar H. Ibarra
Lila Kari

The process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the difficult task of re-arranging gene segments in the correct order and deleting non-coding sequences from an “encrypted” version of a DNA strand, has been modeled and studied so far from the point of view of the computational power of the DNA bio-operations involved. Here we concentrate on a different aspect of the process, by considering only the linear version of the bio-operations, that do not involve thus any circular strands, and by studying the resulting formal operations from a purely language-theoretic point of view. We investigate closure properties of language families under the mentioned bio-operations and study language equations involving them. We also study the decidability of the existence of solutions to equations of the form L♢Y=R, X♢L=R where L and R are given languages, X and Y are unknowns, and ♢ signifies one of the defined bio-operations.

Details DOI