On codes defined by bio-operations. (English) Zbl 1135.92303
Summary: We consider the classes of \(\oplus\)-codes and \(\otimes\)-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 \(\oplus\)-codes and \(\otimes\)-codes from a theoretical perspective, examine their relationships with traditional code classes and consider related decidability problems.
References:
| [1] | Berstel, J.; Perrin, D., Theory of Codes (1996), Available at · Zbl 1022.94506 |
| [2] | Daley, M.; Domaratzki, M., Codes defined by bio-operations, (Calude, C.; Calude, E.; Dinneen, M., Developments in Language Theory 2004. Developments in Language Theory 2004, LNCS, vol. 3340 (2004), Springer), 163-174 · Zbl 1117.68402 |
| [3] | Daley, M.; Ibarra, O.; Kari, L., Closure properties and decision questions of some language classes under ciliate bio-operations, Theoret. Comput. Sci., 306, 1, 19-38 (2003) · Zbl 1060.68060 |
| [4] | Daley, M.; Kari, L., Some properties of ciliate bio-operations, (Ito, M.; Toyama, M., DLT 2002: Developments in Language Theory, Sixth International Conference. DLT 2002: Developments in Language Theory, Sixth International Conference, LNCS, vol. 2450 (2003), Springer), 116-127 · Zbl 1015.68113 |
| [5] | Daley, M.; Kari, L.; McQuillan, I., Families of languages defined by ciliate bio-operations, Theoret. Comput. Sci., 320, 1, 51-69 (2004) · Zbl 1068.68076 |
| [6] | M. Domaratzki, Hairpin structures defined by DNA trajectories, in: Pre-proceedings of DNA 12, Seoul, South Korea, 2006, pp. 11-21; M. Domaratzki, Hairpin structures defined by DNA trajectories, in: Pre-proceedings of DNA 12, Seoul, South Korea, 2006, pp. 11-21 |
| [7] | Domaratzki, M., Characterizing DNA bond shapes using trajectories, (EDS, DLT 2006: Developments in Language Theory. DLT 2006: Developments in Language Theory, LNCS, vol. 4036 (2006), Springer), 180-191 · Zbl 1227.68052 |
| [8] | M. Domaratzki, Bond-free DNA language classes, Nat. Comput. (in press); M. Domaratzki, Bond-free DNA language classes, Nat. Comput. (in press) · Zbl 1130.68061 |
| [9] | Domaratzki, M., Trajectory-based codes, Acta Inf., 40, 6-7, 491-527 (2004) · Zbl 1094.68048 |
| [10] | Haines, L., On free monoids partially ordered by embedding, J. Comb. Theory, 6, 94-98 (1969) · Zbl 0224.20065 |
| [11] | T. Harju, J. Karhumäki, Morphisms, pp. 439-510. In [22]; T. Harju, J. Karhumäki, Morphisms, pp. 439-510. In [22] |
| [12] | Higman, G., Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 2, 3, 326-336 (1952) · Zbl 0047.03402 |
| [13] | Ibarra, O. H., Reversal-bounded multicounter machines and their decision problems, J. Assoc. Comput. Mach., 25, 116-133 (1978) · Zbl 0365.68059 |
| [14] | Ito, M.; Jürgensen, H.; Shyr, H.; Thierrin, G., Outfix and infix codes and related classes of languages, J. Comp. Sys. Sci., 43, 484-508 (1991) · Zbl 0794.68087 |
| [15] | H. Jürgensen, S. Konstantinidis, Codes, pp. 511-600. In [22]; H. Jürgensen, S. Konstantinidis, Codes, pp. 511-600. In [22] |
| [16] | Kari, L., On language equations with invertible operations, Theoret. Comput. Sci., 132, 129-150 (1994) · Zbl 0821.68075 |
| [17] | Kari, L.; Kitto, R.; Thierrin, G., (Codes, Involutions and DNA Encoding. Codes, Involutions and DNA Encoding, LNCS, vol. 2300 (2002), Springer), 376-393 · Zbl 1060.68600 |
| [18] | Kari, L.; Konstantinidis, S.; Losseva, E.; Wozniak, G., Sticky-free and overhang-free DNA languages, Acta. Inf., 40, 2, 119-157 (2003) · Zbl 1072.68044 |
| [19] | Kari, L.; Konstantinidis, S.; Sosík, P., On properties of bond-free DNA languages, Theoret. Comput. Sci., 334, 1-3, 131-159 (2005) · Zbl 1080.68036 |
| [20] | Latteux, M.; Roos, Y., Synchronized shuffle and regular languages, (Karhumäki, J.; etal., Jewels are Forever: Contributions on Theoretical Computer Science in Honour of Arto Salomaa (1999), Springer), 35-44 · Zbl 0944.68105 |
| [21] | Lothaire, M., Combinatorics on Words (1983), Addison-Wesley · Zbl 0514.20045 |
| [22] | (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. I (1997), Springer-Verlag) · Zbl 0866.68057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
