کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429752 | 687667 | 2016 | 48 صفحه PDF | دانلود رایگان |
• The class of recognizable picture languages is characterized by existential monadic second-order logic.
• Logical characterizations of the class of picture languages recognized in linear time on nondeterministic cellular automata.
• This shows the logics involved can be made “local” with respect to the underlying regular structures.
• Hierarchy results among some logical frameworks are deduced from the above.
This paper deals with descriptive complexity of picture languages of any dimension by fragments of existential second-order logic:1) We generalize to any dimension the characterization by Giammarresi et al. (1996) of the class of recognizable picture languages in existential monadic second-order logic.2) We state natural logical characterizations of the class of picture languages of any dimension d≥1d≥1 recognized in linear time on nondeterministic cellular automata, a robust complexity class that contains, for d=1d=1, all the natural NP-complete problems.Our characterizations are essentially deduced from normalization results for first-order and existential second-order logics over pictures.
Journal: Journal of Computer and System Sciences - Volume 82, Issue 6, September 2016, Pages 959–1006