Top

Published in:

2020 | OriginalPaper | Chapter

Simulating Parallel Internal Column Contextual Array Grammars Using Two-Dimensional Parallel Restarting Automata with Multiple Windows

Authors : Abhisek Midya, Frits Vaandrager, D. G. Thomas, Chandrima Ghosh

Published in: Combinatorial Image Analysis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The connection between picture languages and restarting automata has been established in Otto (2014). An interesting class of picture languages generated by parallel contextual array grammars was studied with application in image generation and analysis in Subramanian et al. (2008). In this paper, we introduce a variant of two dimensional restarting automata that accepts a subclass of parallel internal contextual array languages. We show that these automata can simulate parallel internal column contextual array grammars in reverse order.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter 3D-Array Token Petri Nets Generating Tetrahedral Picture Languages

next chapter Grayscale Uncertainty of Projection Geometries and Projections Sets

We consider \(\mathbf{A}\) is a singleton axiom set and \(B \in A\).

Alhazov, A., Fernau, H., Freund, R., Ivanov, S., Siromoney, R., Subramanian, K.: Contextual array grammars with matrix control, regular control languages, and tissue P systems control. Theor. Comput. Sci. 682, 5–21 (2017)MathSciNetCrossRef

Anselmo, M., Giammarresi, D., Madonia, M.: A common framework to recognize two-dimensional languages. Fundamenta Informaticae 171(1–4), 1–17 (2020)MathSciNetMATH

Bunke, H., Sanfeliu, A.: Syntactic and Structural Pattern Recognition: Theory and Applications, vol. 7. World Scientific, New York (1990)CrossRef

Chandra, P.H., Subramanian, K., Thomas, D.: Parallel contextual array grammars and languages. Electron. Notes Discrete Math. 12, 106–117 (2003)MathSciNetCrossRef

Dahlhaus, E., Warmuth, M.K.: Membership for growing context-sensitive grammars is polynomial. J. Comput. Syst. Sci. 33(3), 456–472 (1986)MathSciNetCrossRef

Ehrenfeucht, A., Păun, G., Rozenberg, G.: Contextual grammars and formal languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 237–293. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-662-07675-0_6CrossRef

Fernau, H., Freund, R., Siromoney, R., Subramanian, K.: Non-isometric contextual array grammars and the role of regular control and local selectors. Fundamenta Informaticae 155(1–2), 209–232 (2017)MathSciNetCrossRef

Fernau, H., Paramasivan, M., Schmid, M.L., et al.: Simple picture processing based on finite automata and regular grammars. J. Comput. Syst. Sci. 95, 232–258 (2018)MathSciNetCrossRef

Firschein, O.: Syntactic pattern recognition and applications. Proc. IEEE 71(10), 1231–1231 (1983)CrossRef

10.

Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 215–267. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-59126-6_4CrossRef

11.

Holzer, M.: On fixed and general membership for external and internal contextual languages. In: Developments in Language Theory: Foundations, Applications, and Perspectives, pp. 351–361. World Scientific, New York (2000)

12.

Janar, P., Mráz, F., Páltek, M., Procházka, M., Vogel, J.: Deleting automata with a restart operation. In: 3rd International Conference Developments in Language Theory, DLT, pp. 191–202 (1997)

13.

Jancar, P., Mraz, F., Plátek, M., Procházka, M., Vogel, J.: Restarting automata, marcus grammars and context-free languages. In: Developments in Language Theory, pp. 102–111. World Scientific, New York (1995)

14.

Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) International Symposium on Fundamentals of Computation Theory, pp. 283–292. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60249-6_60CrossRef

15.

Krithivasan, K., Balan, M.S., Rama, R.: Array contextual grammars. In: Recent Topics in Mathematical and Computational Linguistics, pp. 154–168 (2000)

16.

Marcus, S.: Contextual grammars. In: International Conference on Computational Linguistics Coling 1969: Preprint No. 48 (1969)

17.

Midya, A., Thomas, D., Malik, S., Pani, A.K.: Polynomial time learner for inferring subclasses of internal contextual grammars with local maximum selectors. In: Hung, D., Kapur, D. (eds.) International Colloquium on Theoretical Aspects of Computing, pp. 174–191. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67729-3_11CrossRefMATH

18.

Mráz, F., Průša, D., Wehar, M.: Two-dimensional pattern matching against basic picture languages. In: Hospodar, M., Jiraskova, G. (eds.) International Conference on Implementation and Application of Automata, pp. 209–221. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23679-3_17

19.

Otto, F.: Restarting automata for picture languages: a survey on recent developments. In: Holzer, M., Kutrib, M. (eds.) International Conference on Implementation and Application of Automata, pp. 16–41. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08846-4_2CrossRef

20.

Otto, F., Mráz, F.: Extended two-way ordered restarting automata for picture languages. In: Dediu, A.H., Martin-Vide, C., Sierra-Rodriguez, J.L., Truthe, B. (eds.) International Conference on Language and Automata Theory and Applications. pp. 541–552. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04921-2_44

21.

Paun, G.: Marcus Contextual Grammars, vol. 67. Springer, Dordrecht (2013). https://doi.org/10.1007/978-94-015-8969-7CrossRefMATH

22.

Paun, G., Nguyen, X.M.: On the inner contextual grammars. Rev. Roum. Math. Pures Appl. 25(4), 641–651 (1980)MathSciNetMATH

23.

Rama, R., Smitha, T.: Some results on array contextual grammars. Int. J. Pattern Recogn. Artif. Intell. 14(04), 537–550 (2000)CrossRef

24.

Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition. Academic Press, Cambridge (2014)MATH

25.

Rosenfeld, A., Siromoney, R.: Picture languages: a survey. Lang. Design 1(3), 229–245 (1993)

26.

Subramanian, K., Van, D.L., Chandra, P.H., Quyen, N.D.: Array grammars with contextual operations. Fundamenta Informaticae 83(4), 411–428 (2008)MathSciNetMATH

Title: Simulating Parallel Internal Column Contextual Array Grammars Using Two-Dimensional Parallel Restarting Automata with Multiple Windows
Authors: Abhisek Midya
Frits Vaandrager
D. G. Thomas
Chandrima Ghosh
Publisher: Springer International Publishing
Book: Combinatorial Image Analysis
Print ISBN: 978-3-030-51001-5

Electronic ISBN: 978-3-030-51002-2

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-51002-2_8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner