1. Closure Under Reversal of Languages over Infinite Alphabets
- Author
-
Daniel Genkin, Michael Kaminski, and Liat Peterfreund
- Subjects
Discrete mathematics ,Computer science ,Computation ,Structure (category theory) ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,0102 computer and information sciences ,02 engineering and technology ,Nonlinear Sciences::Cellular Automata and Lattice Gases ,01 natural sciences ,Automaton ,Set (abstract data type) ,Closure (mathematics) ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Computer Science::Formal Languages and Automata Theory ,Word (computer architecture) - Abstract
It is shown that languages definable by weak pebble automata are not closed under reversal. For the proof, we establish a kind of periodicity of an automaton’s computation over a specific set of words. The periodicity is partly due to the finiteness of the automaton description and partly due to the word’s structure. Using such a periodicity we can find a word such that during the automaton’s run on it there are two different, yet indistinguishable, configurations. This enables us to remove a part of that word without affecting acceptance. Choosing an appropriate language leads us to the desired result.
- Published
- 2018
- Full Text
- View/download PDF