Abstract
We study properties of a two-dimensional grammar introduced recently for use in document analysis and recognition. The grammar is obtained from the two-dimensional context-free grammar by restricting the form of productions. Variants (ranks) of the grammar with regard to productions complexity are defined. It is suggested that the lowest-rank variant can be considered as a natural generalization of the regular matrix grammar, which in addition has good properties with respect to the membership and emptiness problems. However, it is also showed that the higher-rank variants do not loosen complexity of the context-free grammar too much. There is a conditional lower bound preventing to propose a linear-time parsing algorithm. Moreover, the grammar is able to simulate the 2-counter Minsky machine, which results in non-recursive trade-offs and undecidability of the emptiness problem.
The author was supported by the Czech Science Foundation grant no. 19-21198S.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Álvaro, F., Cruz, F., Sánchez, J.A., Ramos Terrades, O., Benedí, J.M.: Structure detection and segmentation of documents using 2D stochastic context-free grammars. Neurocomputing 150(PA), 147–154 (2015)
Crespi Reghizzi, S., Pradella, M.: A CKY parser for picture grammars. Inf. Process. Lett. 105(6), 213–217 (2008)
Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13(2), 94–102 (1970)
Fernau, H., Paramasivan, M., Schmid, M.L., Thomas, D.G.: Simple picture processing based on finite automata and regular grammars. J. Comput. Syst. Sci. 95, 232–258 (2018)
Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer, New York (1997). https://doi.org/10.1007/978-3-642-59126-6_4
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. In: Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC 1977), STOC 1977, pp. 1–10. ACM, New York (1977)
Lee, L.: Fast context-free grammar parsing requires fast Boolean matrix multiplication. J. ACM 49(1), 1–15 (2002)
Lemaitre, A., Mouchère, H., Camillerapp, J., Coüasnon, B.: Interest of syntactic knowledge for on-line flowchart recognition. In: 9th IAPR International Workshop on Graphics Recognition, 2011, GREC 2011, pp. 85–88 (2011)
Matz, O.: Regular expressions and context-free grammars for picture languages. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 283–294. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0023466
Mráz, F., Průša, D., Wehar, M.: Two-dimensional pattern matching against basic picture languages. In: Hospodár, M., Jirásková, G. (eds.) CIAA 2019. LNCS, vol. 11601, pp. 209–221. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23679-3_17
de Oliveira Oliveira, M., Wehar, M.: Intersection non-emptiness and hardness within polynomial time. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 282–290. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98654-8_23
Průša, D.: Non-recursive trade-offs between two-dimensional automata and grammars. Theor. Comput. Sci. 610, 121–132 (2016)
Průša, D., Fujiyoshi, A.: Rank-reducing two-dimensional grammars for document layout analysis. In: 14th IAPR International Conference on Document Analysis and Recognition (ICDAR 2017), vol. 01, pp. 1120–1125 (2017)
Průša, D., Hlaváč, V.: Mathematical formulae recognition using 2D grammars. In: 9th International Conference on Document Analysis and Recognition (ICDAR 2007), pp. 849–853. IEEE Computer Society (2007)
Průša, D., Reinhardt, K.: Undecidability of the emptiness problem for context-free picture languages. Theor. Comput. Sci. 679, 118–125 (2017)
Radó, T.: On non-computable functions. Bell Syst. Tech. J. 41(3), 877–884 (1962)
Schlesinger, M.I., Hlaváč, V.: Ten Lectures on Statistical and Structural Pattern Recognition (Computational Imaging and Vision), 1st edn. Springer, Dordrecht (2012)
Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Comput. Graph. Image Process. 1(3), 284–307 (1972)
Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: 44th Annual ACM Symposium on Theory of Computing (STOC 2012), pp. 887–898. ACM, New York (2012)
Younger, D.: Recognition of context-free languages in time \(n^3\). Inf. Control 10, 189–208 (1967)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Průša, D. (2020). Complexity of Two-Dimensional Rank-Reducing Grammars. In: Jirásková, G., Pighizzini, G. (eds) Descriptional Complexity of Formal Systems. DCFS 2020. Lecture Notes in Computer Science(), vol 12442. Springer, Cham. https://doi.org/10.1007/978-3-030-62536-8_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-62536-8_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62535-1
Online ISBN: 978-3-030-62536-8
eBook Packages: Computer ScienceComputer Science (R0)