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.
978-3-642-21492-9
Two-dimensional languages.; Lower bound techniques on NFA.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/98632
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact