Publication at Faculty of Mathematics and Physics |
2022
Abstract
By using a stateless deterministic transducer with a window of size 3-by-3 that employs a simple scanning strategy, we reduce a given picture language to a string language. Then we utilize two types of deterministic automata to accept this string language, finite-state acceptors and finite-state acceptors with translucent letters.
In this way, we obtain two classes of picture languages for which the membership problems are easily solvable. We investigate the expressive capacity of these classes as well as their closure properties.