Enforcing Regular Languages

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Genova, Daniela^a | Hoogeboom, Hendrik Jan^{b; *}

Affiliations: [a] Department of Mathematics and Statistics, University of North Florida, Jacksonville, FL 32224, USA. d.genova@unf.edu | [b] LIACS, Leiden University, The Netherlands. h.j.hoogeboom@liacs.leidenuniv.nl

Correspondence: [*] Address for correspondence: Leiden Institute of Advanced Computer Science, P.O. Box 9512, 2300 RA Leiden, The Netherlands.

Abstract: 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).

Keywords: forbidding-enforcing systems, regular languages, (strictly) locally testable, natural computing, biomolecular computing

DOI: 10.3233/FI-2017-1556

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 131-144, 2017