L.Kari, S.Kopecki. Deciding whether a regular language is generated by a splicing system. Journal of
Computer and Systems Sciences, JCSS, vol.84, 2017, 263-287
pdf
R. Karamichalis, L. Kari, S. Konstantinidis, S.Kopecki, S.Solis-Reyes. Additive methods for genomic
signatures.
BMC Bioinformatics, 17:313, 2016.
pdf
Mapping the space of genomic signatures. L.Kari, K.Hill, A.Sayem, R.Karamichalis, N.Bryans, K.Davis,
N.Dattani. PLoS ONE 10(5): e0119815. doi:10.1371/journal.pone.0119815, 2015,
pdf
El.Czeizler, Eu.Czeizler, L.Kari, S.Seki.
An extension of the Lyndon-Schutzenberger result to pseudoperiodic words.
Information and Computation, 209, 2011, 717-730.
pdf
L.Kari, S.Seki.
An improved bound for an extension of Fine and Wilf's theorem, and its optimality.
Fundamenta Informaticae, 101 (3), 2010, 215-236.
(pdf)
L.Adleman, J.Kari, L.Kari, D.Reishus, P.Sosik, The
Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly.
SIAM J. Comput. Volume 38, Issue 6, pp. 2356-2381 (2009)
(pdf)
Self-assembly, the process by which simple objects autonomously come together to form complex structures, has recently become of great practical importance in the context of the developments in nanotechnolodgy and nanocomputation. A systematic study of self-assembly as a mathematical process has been initiated by Adleman. The individual components are modelled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific ``glue'', and two adjacent tiles will stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional ``structures'' such as squares, rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called ribbon: A non-self-crossing sequence of tiles on the plane, in which successive tiles are adjacent along an edge, and abutting edges of consecutive tiles have matching glues. We namely prove that, given a finite set of tiles with glues (infinite supply of each tile type available) it is undecidable whether or not there exists an infinite ribbon that can be formed with these tiles. The result settles a decade-old open problem formerly known as the ``unlimited infinite snake problem''. An immediate consequence is the undecidability of existence of arbitrarily large structures self-assembled using tiles from a given tile set.
L. Kari, S. Seki,
On pseudoknot-bordered words and their properties,
Journal of Computer and System Sciences, 75 (2009) 113-121.
pdf
L. Kari, K. Mahalingam, S. Seki,
Twin-roots of words and their properties, Theoretical Computer Science, vol. 410, nr.24-25 (2009),
2393-2400.
pdf
L.Kari, G.Rozenberg. The many facets of natural computing. Communications
of the ACM, Oct.2008, vol.51, no.10, 72-83 .
Cover Story of
Communications of the ACM. (pdf file)
pdf file of the paper with no pictures but
with extended reference list .
E.Czeizler, L.Kari, S.Seki.
On a Special Class of Primitive Words. MFCS 2008: 265-277
pdf
L.Kari, K.Mahalingam, Involutively bordered words, International
Journal of Foundations of Computer Science, 18(5) 2007, 1089-1106.
pdf
L.Kari, S.Konstantinidis, P.Sosik.
On properties of bond-free DNA languagesThe computation language of a DNA-based system consists of all the words (DNA strands) that can appear during any biocomputation of the system. In this paper we investigate properties of such languages which ensure that their words will not form undesirable bonds when used in DNA computations. The pioneering aspect and contribution of this research is to establish a link between classical coding theory and DNA computing. It turns out that the newly defined notions of DNA compliant and sticky-free languages are theoretically elegant generalizations of classical types of codes. Furthermore, the use of such languages as input data ensures that the DNA computations will proceed error-free, therefore their study has practical relevance for experimental DNA computing.
L. Kari, S. Konstantinidis: Language Equations, Maximality and Error-detection. J. of Computer and System Sciences 70 (2005), 157-178.
pdf
Y.Wang, K.Hill, S.Singh, L.Kari.
The spectrum of genomic signatures: From dinucleotides to Chaos Game Representation.
GENE, 346 (2005), 173-185. pdf
In the post genomic era, access to complete genome sequence data for numerous diverse species has triggered multiple avenues for examining and comparing primary DNA sequence organization of entire genomes. Previously, the concept of a genomic signature was introduced with the observation of species-type specific Dinucleotide Relative Abundance Profiles (DRAPs); dinucleotides were identified as the subsequence with the greatest bias in representation in a majority of genomes. Herein, we demonstrate that DRAP is one particular genomic signature contained within a broader spectrum of signatures. In this spectrum, an alternative genomic signature, Chaos Game Representation (CGR), provides a unique visualization of patterns in sequence organization. A genomic signature is associated with a particular integer order or subsequence length that represents a measure of the resolution or granularity in the analysis of primary DNA sequence organization. We quantitatively explore the organizational information provided by genomic signatures of different orders through different distance measures, including a novel Image Distance. The Image Distance and other existing distance measures are evaluated by comparing the phylogenetic trees they generate for 26 complete mitochondrial genomes from a diversity of species. The phylogenetic tree generated by the Image Distance is compatible with the known relatedness of species. Quantitative evaluation of the spectrum of genomic signatures may be used to ultimately gain insight into the determinants and biological relevance of the genome signatures.
L.Kari, L.F.Landweber. Computational power of gene rearrangement.
Proc. DNA 5, DIMACS Series, 54(2000), 207-216
pdf , ps
Ciliates are a diverse group of a few thousand types of unicellular eukaryotes distinguished by the presence of two nuclei: an active macronucleus and a functionally inert micronucleus which contributes only to sexual reproduction. The macronuclear DNA forms after sexual reproduction from the micronuclear DNA by recombinations that accomplish a rearrangement of gene fragments in the desired order and the deletion of non-coding sequences. In this paper we develop a model for the guided homologous recombinations that take place during gene rearrangement and prove that it has the computational power of a Turing machine. This is a proof of concept indicating that unicellular organisms may have the capacity to perform any computation carried out by an electronic computer.
L.Landweber, L.Kari. The evolution of cellular computing:
nature's solution to a computational problem. Biosystems 52(1999) 3-13.
pdf
L.Kari. DNA computing -- The arrival of biological mathematics.
The Mathematical Intelligencer, 19(1997), 9--22.
pdf
L.Kari.
On Insertion and Deletion in Formal Languages.
Ph.D. Thesis, University of Turku, 1991.
Cover page ,
Title page ,
ISBN ,
Acknowledgements ,
Part I ,
Part II .
G.Paun, L.Santean.
Parallel communicating grammar systems-- the regular case.
Analele Universitatii din Bucuresti, Seria matematica-informatica,nr.2, 1989, 55-63. pdf