CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThe paper deals with some classes of two-dimensional recognizable languages of ``high complexity'', in a sense specified in the paper and motivated by some necessary conditions holding for recognizable and unambiguous languages. For such classes we can solve some open questions related to unambiguity, finite ambiguity and complementation. Then we reformulate a necessary condition for recognizability stated by O. Matz, introducing a new complexity function. We solve an open question proposed by O. Matz, showing that all the known necessary conditions for recognizability of a language and its complement are not sufficient. The proof relies on a family of languages defined by functions.
| Titolo: | Classes of two-dimensional languages and recognizability conditions |
| Autori interni: | |
| Data di pubblicazione: | 2010 |
| Rivista: | |
| Handle: | http://hdl.handle.net/20.500.11769/35524 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/20.500.11769/35524
Copyright © 2020