Expressiveness and complexity of regular pure two-dimensional context-free languages

References

• Bersani , M. M. , Frigeri , A. and Cherubini , A. 2011 . “ On some classes of 2D languages and their relations, in IWCIA: International Workshop on Combinatorial Image Analysis ” . In Lecture Notes in Computer Science , Edited by: Aggarwal , J. K. , Barneva , R. P. , Brimkov , V. E. , Koroutchev , K. and Korutcheva , E. Vol. 6636 , 222 – 234 . Berlin : Springer .
   Google Scholar
• Blum , M. and Hewitt , C. Automata on a 2-Dimensional Tape . Proceedings of the 8th Annual Symposium on Switching and Automata Theory (SWAT 1967), FOCS ’67 . October 18–20 , Texas . pp. 155 – 160 . Los Alamitos, CA Available at http://www.computer.org/csdl/proceedings/focs/1967/4847/00/index.html
   Google Scholar
• Cherubini , A. , Crespi-Reghizzi , S. , Pradella , M. and San Pietro , P. 2006 . Picture languages: Tiling systems versus tile rewriting grammars . Theor. Comput. Sci. , 356 : 90 – 103 . (doi:10.1016/j.tcs.2006.01.038)
   Web of Science ®Google Scholar
• Crespi-Reghizzi , S. and Pradella , M. 2005 . Tile rewriting grammars and picture languages . Theor. Comput. Sci. , 340 : 257 – 272 . (doi:10.1016/j.tcs.2005.03.041)
   Web of Science ®Google Scholar
• Dahlhaus , E. and Warmuth , M. 1986 . “ Membership for growing context sensitive grammars is polynomial, in CAAP: Colloquium on Trees in Algebra and Programming ’86 ” . In Lecture Notes in Computer Science , Edited by: Franchi-Zannettacci , P. Vol. 214 , 85 – 99 . Berlin : Springer .
   Google Scholar
• Giammarresi , D. and Restivo , A. 2008 . “ Ambiguity and complementation in recognizable two-dimensional languages, in IFIP – TCS: International Federation for Information Processing – Theoretical Computer Science 2008 ” . Edited by: Ausiello , G. , Karhumäki , J. , Mauri , G. and Ong , L. 5 – 20 . Berlin : Springer .
   Google Scholar
• Greibach , S. A. and Hopcroft , J. E. 1969 . Scattered context grammars . J. Comput. Syst. Sci. , 3 : 233 – 247 . (doi:10.1016/S0022-0000(69)80015-2)
   Google Scholar
• Inoue , K. and Nakamura , A. 1977 . Some properties of two-dimensional on-line tessellation acceptors . Inf. Sci. , 13 : 95 – 121 . (doi:10.1016/0020-0255(77)90023-8)
   Web of Science ®Google Scholar
• Karp , R. M. 1972 . “ Reducibility among combinatorial problems, in Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations ” . In The IBM Research Symposia Series , Edited by: Miller , R. E. and Thatcher , J. W. 85 – 103 . New York, NY : Plenum Press . R.E. Miller and J.W. Thatcher, eds., Plenum Press, 1972, pp. 85–103.
   Google Scholar
• Matz , O. 1997 . “ Regular expressions and context-free grammars for picture languages, in STACS 97: 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27–March 1, 1997 Proceedings ” . In Lecture Notes in Computer Science , Edited by: Reischuk , R. and Morvan , M. Vol. 1200 , 283 – 294 . Berlin : Springer .
   Google Scholar
• Pradella , M. , Cherubini , A. and Crespi-Reghizzi , S. 2011 . A unifying approach to picture grammars . Inf. Comput. , 209 : 1246 – 1267 . (doi:10.1016/j.ic.2011.07.001)
   Web of Science ®Google Scholar
• D. Prusa, Two-dimensional languages, Ph.D. thesis, Charles University, Faculty of Mathematics and Physics, Czech Republic, 2004.
   Google Scholar
• Pruša , D. and Hlavác , V. 2006 . “ 2D context-free grammars: Mathematical formulae recognition, in Prague Stringology Conference 2006 ” . Edited by: Holub , J. and Zdárek , J. 77 – 89 . Prague : Czech Technical University .
   Google Scholar
• Siromoney , G. , Siromoney , R. and Krithivasan , K. 1972 . Abstract families of matrices and picture languages . Comput. Graph. Image Process. , 1 : 284 – 307 . (doi:10.1016/S0146-664X(72)80019-4)
   Google Scholar
• Siromoney , G. , Siromoney , R. and Krithivasan , K. 1973 . Picture languages with array rewriting rules . Inf. Control , 23 ( 5 ) : 447 – 470 . (doi:10.1016/S0019-9958(73)90573-1)
   Google Scholar
• Subramanian , K. G. , Nagar , A. K. and Geethalakshmi , M. 2008 . “ Pure 2D picture grammars (P2DPG) and P2DPG with regular control, in IWCIA: International Workshop on Combinatorial Image Analysis 2008 ” . In Lecture Notes in Computer Science , Edited by: Brimkov , V. E. , Barneva , R. P. and Hauptman , H. A. Vol. 4958 , 330 – 341 . Berlin : Springer .
   Google Scholar
• Subramanian , K. G. , Ali , R. M. , Geethalakshmi , M. and Nagar , A. K. 2009 . Pure 2D picture grammars and languages . Discrete Appl. Math. , 157 : 3401 – 3411 . (doi:10.1016/j.dam.2009.02.017)
   Web of Science ®Google Scholar