Displaying similar documents to “The finite automata approaches in stringology”

Automata with modulo counters and nondeterministic counter bounds

Daniel Reidenbach, Markus L. Schmid (2014)

Kybernetika

Similarity:

We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically...

Positioned agents in eco-grammar systems with border markers and pure regulated grammars

Miroslav Langer, Alica Kelemenová (2012)

Kybernetika

Similarity:

In this paper we follow our previous research in the field of positioned agents in the eco-grammar systems and pure grammars. We extend model of the positioned eco-grammar systems by boundary markers and we introduce bordered positioned eco-grammar systems (BPEG systems, for short) and that way we show one of the possible answers to the question stated in [9]. Namely we compare generative power of the BPEG systems with three types of pure regulated grammars with appearance checking. ...