The main problem in this paper is to find feasible conditions to prove/disprove that a given two-dimensional language is tiling recognizable. We focus on two known conditions necessarily satisfied by a recognizable language, that are based on the idea to reduce the problem from picture to string languages. We emphasize that they are grounded on two lower bound techniques for regular string languages. Starting from a stronger lower bound, named the nondeterministic message complexity technique, we are able to state a new necessary condition for the recognizability of two-dimensional languages. We compare the three conditions and find that the new one extends the previous two yielding a greater accuracy.
Comparing Necessary Conditions for Recognizability of Two- dimensional Languages
MADONIA, Maria Serafina
2011-01-01
Abstract
The main problem in this paper is to find feasible conditions to prove/disprove that a given two-dimensional language is tiling recognizable. We focus on two known conditions necessarily satisfied by a recognizable language, that are based on the idea to reduce the problem from picture to string languages. We emphasize that they are grounded on two lower bound techniques for regular string languages. Starting from a stronger lower bound, named the nondeterministic message complexity technique, we are able to state a new necessary condition for the recognizability of two-dimensional languages. We compare the three conditions and find that the new one extends the previous two yielding a greater accuracy.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
