6533b82efe1ef96bd1293ac3

RESEARCH PRODUCT

RECOGNIZABLE PICTURE LANGUAGES

Antonio RestivoDora Giammarresi

subject

Finite-state machinebusiness.industrymedia_common.quotation_subjectClosure (topology)Abstract family of languagesComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)AmbiguityOntology languageCone (formal languages)DecidabilityPhilosophy of languageTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESArtificial IntelligenceComputer Science::Programming LanguagesComputer Vision and Pattern RecognitionArtificial intelligencebusinessComputer Science::Formal Languages and Automata TheorySoftwareMathematicsmedia_common

description

The purpose of this paper is to propose a new notion of recognizability for picture (two-dimensional) languages extending the characterization of one-dimensional recognizable languages in terms of local languages and alphabetic mappings. We first introduce the family of local picture languages (denoted by LOC) and, in particular, prove the undecidability of the emptiness problem. Then we define the new family of recognizable picture languages (denoted by REC). We study some combinatorial and language theoretic properties of REC such as ambiguity, closure properties or undecidability results. Finally we compare the family REC with the classical families of languages recognized by four-way automata.

yearjournalcountryeditionlanguage
1992-08-01International Journal of Pattern Recognition and Artificial Intelligence
https://doi.org/10.1142/s021800149200014x