Publication | Closed Access
RECOGNIZABLE PICTURE LANGUAGES
166
Citations
0
References
1992
Year
EngineeringPushdown AutomatonSpeech RecognitionCombinatorics On WordLanguage DocumentationImage AnalysisPattern RecognitionTree AutomatonDiscrete MathematicsLanguage StudiesCharacter RecognitionMachine VisionRecognizable Picture LanguagesLocal Picture LanguagesComputer ScienceMultimodal TranslationComputer VisionNew FamilyFormal MethodsLanguage RecognitionAutomaton OperationFamily RecLinguisticsComputability Theory
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.