Enforcing Regular Languages

• Autorzy: Genova, D. , Hoogeboom, H. J.
• Języki publikacji: EN

Abstrakty

EN

We investigate regular languages in the context of the forbidding-enforcing systems introduced by Ehrenfeucht and Rozenberg in the variant where one fe-system defines a single language. In general, these systems may have infinite sets of rules, allowing one to define arbitrary languages. On the other hand when restricted to finite sets, one obtains a strict subclass of the regular languages, between the strictly locally testable and locally testable languages. We further investigate classes of enforcing systems that characterize the regular languages. These systems have infinite sets of enforcers, but can be defined using regular languages (finite state automata).

Słowa kluczowe

EN

forbidding-enforcing systems; regular languages; locally testable; natural computing; biomolecular computing

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 131--144
• Opis fizyczny: Bibliogr. 24 poz.

Twórcy

autor

Genova, D.

• Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224, USA,

autor

Hoogeboom, H. J.

• LIACS, Leiden University, The Netherlands,

Bibliografia

• [1] Adleman L. Molecular computation of solutions to combinatorial problems, Science 1994;266:1021–1024. doi:10.1126/science.7973651
• [2] Bonizzoni P, Mauri G. Regular splicing languages and subclasses, Theoretical Computer Science 2005;340:349–363. doi:10.1016/j.tcs.2005.03.035
• [3] Brijder R, Hoogeboom HJ. The algebra of gene assembly in ciliates, in: N. Jonoska, M. Saito (eds.) Discrete and Topological Models in Molecular Biology, Natural Computing Series, Springer Berlin Heidelberg, 2014 pp. 289–307. doi:10.1007/978-3-642-40193-0_13
• [4] Cavaliere M, Jonoska N. Forbidding and enforcing in membrane computing, Natural Computing 2003;2:215–228. doi:10.1023/A:1025492906773
• [5] Ehrenfeucht A, Harju T, Petre I, Prescott DM, Rozenberg G. Computation in Living Cells: Gene Assembly in Ciliates. Springer, Berlin, 2003. ISBN-3540407952, 9783540407959.
• [6] Ehrenfeucht A, Hoogeboom HJ, Rozenberg G, van Vugt N. Sequences of languages in forbidding-enforcing families, Soft Computing 2001;5:121–125. doi:10.1007/s00500000007
• [7] Ehrenfeucht A, Hoogeboom HJ, Rozenberg G, van Vugt N. Forbidding and enforcing, in: E. Winfree, D.K. Gifford (eds.) DNA Based Computers V. AMS DIMACS 54, Providence, RI, 2001 pp. 195–206.
• [8] Ehrenfeucht A, Rozenberg G. Forbidding-enforcing systems, Theoretical Computer Science 2003;292:611–638. doi:10.1016/S0304-3975(01)00088-3
• [9] Franco G, Jonoska N. Forbidding and enforcing conditions in DNA self-assembly of graphs, Nanotechnology: Science and Computation, Natural Computing Series 2006 pp. 105–118. doi:10.1007/3-540-30296-4_6
• [10] Genova D. Defining languages by forbidding-enforcing systems, Models of Computation in Context, Computability in Europe (CiE 2011), Lecture Notes in Computer Science 6735, 2011 pp. 92–101. doi: 10.1007/978-3-642-21875-0_10
• [11] Genova D. Forbidding sets and normal forms of Language forbidding-enforcing systems, Language and Automata Theory and Applications (LATA 2012), Lecture Notes in Computer Science 7183, 2012 pp. 289–300. doi:10.1007/978-3-642-28332-1_25
• [12] Genova D. Language forbidding-enforcing systems defining DNA codewords, Computability in Europe CiE 2013, Lecture Notes in Computer Science 7921, 2013 pp. 220–229. doi:10.1007/978-3-642-39053-125
• [13] Genova D, Hoogeboom HJ. Finite language forbidding-enforcing systems, Unveiling Dynamics and Complexity, Computability in Europe (CiE 2017), Lecture Notes in Computer Science 10307, 2017 pp. 258–269. doi:10.1007/978-3-319-58741-7_25
• [14] Genova D, Jonoska N. Defining structures through forbidding and enforcing constraints, Physica B: Condensed Matter 2007;394:306–310. doi:10.1016/j.physb.2006.12.069
• [15] Genova D, Jonoska N. Forbidding and enforcing on graphs, Theoretical Computer Science 2012;429:108–117. doi:10.1016/j.tcs.2011.12.029
• [16] Genova D, Jonoska N. Topological properties of forbidding-enforcing systems, Journal of Automata, Languages and Combinatorics 2006;11:375–397.
• [17] Genova D, Mahalingam K. Generating DNA code words using forbidding and enforcing systems, Theory and Practice in Natural Computing (TPNC 2012), Lecture Notes in Computer Science 7505, 2012 pp. 289–300. doi:10.1007/978-3-642-33860-1-13
• [18] McNaughton R, Papert S. Counter-Free Automata, MIT Press, Cambridge, MA, 1971. ISBN-0262130769.
• [19] Head T. Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors, Bulletin Mathematical Biology 1987;49:737–759. doi:10.1007/BF02481771
• [20] Head T. Splicing representations of strictly locally testable languages, Discrete Applied Mathematics 1998;87:139–147. doi:10.1016/S0166-218X(98)00053-5
• [21] Lyndon RC, Schützenberger MP. The equation aM=bNcP in a free group. Michigan Mathematical Journal 1962;9:289–298. doi:10.1307/mmj/1028998766
• [22] Păun G, Rozenberg G, Salomaa A. DNA Computing–New Computing Paradigms, Springer, Berlin, 1998. doi:10.1007/978-3-662-03563-4.
• [23] Păun G, Rozenberg G, Salomaa A. (Eds.) The Oxford Handbook of Membrane Computing, Oxford University Press, 2009. ISBN-978-0-19-955667-0
• [24] Rozenberg G, Bäck T, Kok NJ (Eds.) Handbook of Natural Computing, 4 vols, Springer, Heidelberg, 2012. ISBN-978-3-540-92909-3

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).

Identyfikatory

DOI

10.3233/FI-2017-1556