Abstract
In [2, 16] a new method of description of pictures of digitized rectangular arrays is introduced based on contextual grammars, called parallel internal contextual array grammars. In this paper, we pay our attention on parallel internal column contextual array grammars and observe that the languages generated by these grammars are not inferable from positive data only. We define two subclasses of parallel internal column contextual array languages, namely, k-uniform and strictly parallel internal column contextual languages which are incomparable and not disjoint classes and provide identification algorithms to learn these classes.
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
Notes
- 1.
In an 1-sided contextual rule either left context is \(\varLambda \) or right context is \(\varLambda \).
References
Chandra, H., Martin-Vide, C., Subramanian, K.G., Van, D.L., Wang, P.S.P.: Parallel contextual array grammars and trajectories. In: Chen, C.H., Wang, P.S.P. (eds.) Handbook of Pattern Recognition and Computer Vision, 3rd edn., pp. 55-70 (2004)
Chandra, H., Subramanian, K.G., Thomas, D.G.: Parallel contextual array grammars and languages. Electron. Notes Discrete Math. 12, 106–117 (2003)
Ehrenfeucht, A., Paun, G., Rozenberg, G.: Contextual grammars and formal languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Language, vol. 2, pp. 237–293 (1997)
Emerald, J.D., Subramanian, K.G., Thomas, D.G.: Inferring subclasses of contextual languages. In: Oliveira, A.L. (ed.) ICGI 2000. LNCS, vol. 1891, pp. 65–74. Springer, Heidelberg (2000). doi:10.1007/978-3-540-45257-7_6
Gold, E.M.: Language identification in the limit. Inf. Control 10, 447–474 (1967)
Fernau, H., Freund, R., Holzer, M.: Representations of recursively enumerable array languages by contextual array grammars. Fundamenta Informatica 64, 159–170 (2005)
Fernau, H., Freund, R., Siromoney, R., Subramanian, K.G.: Contextual array grammars with matrix and regular control. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 98–110. Springer, Cham (2016). doi:10.1007/978-3-319-41114-9_8
Fernau, H., Freund, R., Siromoney, R., Subramanian, K.G.: Non-isometric contextual array grammars with regular control and local selectors. In: Durand-Lose, J., Nagy, B. (eds.) MCU 2015. LNCS, vol. 9288, pp. 61–78. Springer, Cham (2015). doi:10.1007/978-3-319-23111-2_5
Haussler, D.: Insertion and iterated insertion as operations on formal languages. Ph.D. Thesis, University of Colorado, Boulder (1982)
Kari, L.: Contextual insertions/deletions and computability. Inf. Comput. 1, 47–61 (1996)
Krithivasan, K., Balan, M.S., Rama, R.: Array contextual grammars. In: Martin-Vide, C., Paun, G. (eds.) Recent Topics in Mathematical and Computational Linguistics, pp. 154-168 (2000)
Lalitha, D., Rangarajan, K., Thomas, D.G.: Petri net generating hexagonal arrays. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds.) IWCIA 2011. LNCS, vol. 6636, pp. 235–247. Springer, Heidelberg (2011). doi:10.1007/978-3-642-21073-0_22
Marcus, S.: Contextual grammars. Revue Roumane de Mathematiques Pures et Appliques 14(10), 1525–1534 (1969)
Rama, R., Smitha, T.A.: Some results on array contextual grammars. Int. J. Pattern Recogn. Artif. Intell. 14, 537–550 (2000)
Rosenfield, A., Siromoney, R.: Picture languages - a survey. Lang. Design 1, 229–245 (1993)
Subramanian, K.G., Van, D.L., Chandra, P.H., Quyen, N.D.: Array grammars with contextual operations. Fundamenta Informaticae 83, 1–18 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Midya, A., Thomas, D.G., Pani, A.K., Malik, S., Bhatnagar, S. (2017). Polynomial Time Algorithm for Inferring Subclasses of Parallel Internal Column Contextual Array Languages. In: Brimkov, V., Barneva, R. (eds) Combinatorial Image Analysis. IWCIA 2017. Lecture Notes in Computer Science(), vol 10256. Springer, Cham. https://doi.org/10.1007/978-3-319-59108-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-59108-7_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59107-0
Online ISBN: 978-3-319-59108-7
eBook Packages: Computer ScienceComputer Science (R0)