Displaying similar documents to “On a Hedlund's theorem and place-dependent cellular automata.”

The finite automata approaches in stringology

Jan Holub (2012)

Kybernetika

Similarity:

We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).

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. ...