{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:48:38Z","timestamp":1743054518470,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031236112"},{"type":"electronic","value":"9783031236129"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-23612-9_10","type":"book-chapter","created":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T02:36:12Z","timestamp":1672540572000},"page":"154-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Myhill-Nerode Theorem for\u00a0Finite State Matrix Automata and\u00a0Finite Matrix Languages"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5692-565X","authenticated-orcid":false,"given":"Abhisek","family":"Midya","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6327-8446","authenticated-orcid":false,"given":"D. G.","family":"Thomas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"3","key":"10_CR1","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0019-9958(64)90294-3","volume":"7","author":"V Amar","year":"1964","unstructured":"Amar, V., Putzolu, G.: On a family of linear grammars. Inf. Control 7(3), 283\u2013291 (1964)","journal-title":"Inf. Control"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987)","journal-title":"Inf. Comput."},{"issue":"2","key":"10_CR3","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF00116034","volume":"5","author":"D Angluin","year":"1990","unstructured":"Angluin, D.: Negative results for equivalence queries. Mach. Learn. 5(2), 121\u2013150 (1990)","journal-title":"Mach. Learn."},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2016.07.031","volume":"650","author":"D Angluin","year":"2016","unstructured":"Angluin, D., Fisman, D.: Learning regular omega languages. Theoret. Comput. Sci. 650, 57\u201372 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Angluin, D., Kharitonov, M.: When won\u2019t membership queries help? In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 444\u2013454 (1991)","DOI":"10.1145\/103418.103420"},{"issue":"1\u20134","key":"10_CR6","first-page":"1","volume":"171","author":"M Anselmo","year":"2020","unstructured":"Anselmo, M., Giammarresi, D., Madonia, M.: A common framework to recognize two-dimensional languages. Fund. Inform. 171(1\u20134), 1\u201317 (2020)","journal-title":"Fund. Inform."},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/3-540-59119-2_193","volume-title":"Computational Learning Theory","author":"F Bergadano","year":"1995","unstructured":"Bergadano, F., Varricchio, S.: Learning behaviors of automata from shortest counterexamples. In: Vit\u00e1nyi, P. (ed.) EuroCOLT 1995. LNCS, vol. 904, pp. 380\u2013391. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-59119-2_193"},{"issue":"4","key":"10_CR8","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/S0895480198340943","volume":"13","author":"A Birkendorf","year":"2000","unstructured":"Birkendorf, A., B\u00f6ker, A., Simon, H.U.: Learning deterministic finite automata from smallest counterexamples. SIAM J. Discret. Math. 13(4), 465\u2013491 (2000)","journal-title":"SIAM J. Discret. Math."},{"key":"10_CR9","doi-asserted-by":"publisher","DOI":"10.1142\/0580","volume-title":"Syntactic and Structural Pattern Recognition: Theory and Applications","author":"H Bunke","year":"1990","unstructured":"Bunke, H., Sanfeliu, A.: Syntactic and Structural Pattern Recognition: Theory and Applications, vol. 7. World Scientific, Singapore (1990)"},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s00165-016-0355-5","volume":"28","author":"S Cassel","year":"2016","unstructured":"Cassel, S., Howar, F., Jonsson, B., Steffen, B.: Active learning for extended finite state machines. Formal Aspects Comput. 28(2), 233\u2013263 (2016). https:\/\/doi.org\/10.1007\/s00165-016-0355-5","journal-title":"Formal Aspects Comput."},{"key":"10_CR11","doi-asserted-by":"publisher","unstructured":"Cavalcanti, A., Dams, D.: FM 2009: Formal Methods: Second World Congress, Eindhoven, The Netherlands, November 2\u20136, 2009, Proceedings, vol. 5850. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-05089-3","DOI":"10.1007\/978-3-642-05089-3"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.jcss.2017.07.011","volume":"95","author":"H Fernau","year":"2018","unstructured":"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\u2013258 (2018)","journal-title":"J. Comput. Syst. Sci."},{"issue":"10","key":"10_CR13","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1109\/PROC.1983.12755","volume":"71","author":"O Firschein","year":"1983","unstructured":"Firschein, O.: Syntactic pattern recognition and applications. Proc. IEEE 71(10), 1231\u20131231 (1983)","journal-title":"Proc. IEEE"},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-59126-6_4","volume-title":"Handbook of Formal Languages","author":"D Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 215\u2013267. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59126-6_4"},{"issue":"2","key":"10_CR15","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/BF01692513","volume":"2","author":"S Ginsburg","year":"1968","unstructured":"Ginsburg, S., Spanier, E.H.: Control sets on grammars. Math. Syst. Theory 2(2), 159\u2013177 (1968)","journal-title":"Math. Syst. Theory"},{"issue":"5","key":"10_CR16","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold, E.M.: Language identification in the limit. Inf. Control 10(5), 447\u2013474 (1967)","journal-title":"Inf. Control"},{"issue":"2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(91)90016-X","volume":"43","author":"O Habarra","year":"1991","unstructured":"Habarra, O., Jiang, T.: Learning regular languages from counterexamples. J. Comput. Syst. Sci. 43(2), 299\u2013316 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/568438.568455","volume":"32","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60\u201365 (2001)","journal-title":"ACM SIGACT News"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-319-11164-3_26","volume-title":"Runtime Verification","author":"M Isberner","year":"2014","unstructured":"Isberner, M., Howar, F., Steffen, B.: The TTT algorithm: a redundancy-free approach to active automata learning. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 307\u2013322. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11164-3_26"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(97)00016-9","volume":"185","author":"T Koshiba","year":"1997","unstructured":"Koshiba, T., M\u00e4kinen, E., Takada, Y.: Learning deterministic even linear languages from positive examples. Theoret. Comput. Sci. 185(1), 63\u201379 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10_CR21","first-page":"175","volume":"25","author":"E M\u00e4kinen","year":"1996","unstructured":"M\u00e4kinen, E.: A note on the grammatical inference problem for even linear languages. Fund. Inform. 25(2), 175\u2013182 (1996)","journal-title":"Fund. Inform."},{"issue":"1","key":"10_CR22","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0304-3975(96)00312-X","volume":"183","author":"O Maler","year":"1997","unstructured":"Maler, O., Staiger, L.: On syntactic congruences for $$\\omega $$-languages. Theoret. Comput. Sci. 183(1), 93\u2013112 (1997)","journal-title":"Theoret. Comput. Sci."},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-319-67729-3_11","volume-title":"Theoretical Aspects of Computing- ICTAC 2017","author":"A Midya","year":"2017","unstructured":"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.) Theoretical Aspects of Computing- ICTAC 2017. Lecture Notes in Computer Science, vol. 10580, pp. 174\u2013191. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-67729-3_11"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-319-59108-7_13","volume-title":"Combinatorial Image Analysis","author":"A Midya","year":"2017","unstructured":"Midya, A., Thomas, D.G., Pani, A.K., Malik, S., Bhatnagar, S.: Polynomial time algorithm for inferring subclasses of parallel internal column contextual array languages. In: Brimkov, V.E., Barneva, R.P. (eds.) IWCIA 2017. LNCS, vol. 10256, pp. 156\u2013169. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-59108-7_13"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-030-51002-2_8","volume-title":"Combinatorial Image Analysis","author":"A Midya","year":"2020","unstructured":"Midya, A., Vaandrager, F., Thomas, D.G., Ghosh, C.: Simulating parallel internal column contextual array grammars using two-dimensional parallel restarting automata with multiple windows. In: Luki\u0107, T., Barneva, R.P., Brimkov, V.E., \u010comi\u0107, L., Sladoje, N. (eds.) IWCIA 2020. LNCS, vol. 12148, pp. 106\u2013122. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51002-2_8"},{"key":"10_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-030-23679-3_17","volume-title":"Implementation and Application of Automata","author":"F Mr\u00e1z","year":"2019","unstructured":"Mr\u00e1z, F., Pr\u016f\u0161a, D., Wehar, M.: Two-dimensional pattern matching against basic picture languages. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G. (eds.) CIAA 2019. LNCS, vol. 11601, pp. 209\u2013221. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-23679-3_17"},{"issue":"2","key":"10_CR27","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0019-9958(64)90087-7","volume":"7","author":"R Narasimhan","year":"1964","unstructured":"Narasimhan, R.: Labeling schemata and syntactic descriptions of pictures. Inf. Control 7(2), 151\u2013179 (1964)","journal-title":"Inf. Control"},{"key":"10_CR28","unstructured":"Radhakrishnan, V., Chakravarthy, V., Krithivasan, K.: Some properties of matrix grammars- parallel image analysis. In: International Work shop on Parallel Image Processing and Analysis-Theory and Applications, pp. 213\u2013225 (1999)"},{"issue":"1","key":"10_CR29","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0031-3203(88)90071-4","volume":"21","author":"V Radhakrishnan","year":"1988","unstructured":"Radhakrishnan, V., Nagaraja, G.: Inference of even linear grammars and its application to picture description languages. Pattern Recogn. 21(1), 55\u201362 (1988)","journal-title":"Pattern Recogn."},{"issue":"2","key":"10_CR30","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/inco.1993.1021","volume":"103","author":"RL Rivest","year":"1993","unstructured":"Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. Inf. Comput. 103(2), 299\u2013347 (1993)","journal-title":"Inf. Comput."},{"key":"10_CR31","volume-title":"Picture Languages: Formal Models for Picture Recognition","author":"A Rosenfeld","year":"2014","unstructured":"Rosenfeld, A.: Picture Languages: Formal Models for Picture Recognition. Academic Press, Cambridge (2014)"},{"issue":"3","key":"10_CR32","first-page":"229","volume":"1","author":"A Rosenfeld","year":"1993","unstructured":"Rosenfeld, A., Siromoney, R.: Picture languages-a survey. Lang. Des. 1(3), 229\u2013245 (1993)","journal-title":"Lang. Des."},{"key":"10_CR33","unstructured":"Salomaa, A.: On grammars with restricted use of productions. Suomalainen Tiedeakatemia (1969)"},{"key":"10_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/3-540-58473-0_135","volume-title":"Grammatical Inference and Applications","author":"JM Sempere","year":"1994","unstructured":"Sempere, J.M., Garc\u00eda, P.: A characterization of even linear languages and its application to the learning problem. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS, vol. 862, pp. 38\u201344. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58473-0_135"},{"issue":"3","key":"10_CR35","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/S0146-664X(72)80019-4","volume":"1","author":"G Stromoney","year":"1972","unstructured":"Stromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Comput. Graph. Image Process. 1(3), 284\u2013307 (1972)","journal-title":"Comput. Graph. Image Process."},{"issue":"4","key":"10_CR36","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(88)90208-6","volume":"28","author":"Y Takada","year":"1988","unstructured":"Takada, Y.: Grammatical inference for even linear languages based on control sets. Inf. Process. Lett. 28(4), 193\u2013199 (1988)","journal-title":"Inf. Process. Lett."},{"key":"10_CR37","unstructured":"Takada, Y.: Algorithmic learning theory of formal languages and its applications. Ph.D. thesis, International Institute for Advanced Study of Social Information Science $$\\ldots $$ (1992)"},{"issue":"1","key":"10_CR38","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/inco.1995.1163","volume":"123","author":"Y Takada","year":"1995","unstructured":"Takada, Y.: A hierarchy of language families learnable by regular language learning. Inf. Comput. 123(1), 138\u2013145 (1995)","journal-title":"Inf. Comput."},{"key":"10_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-60217-8_15","volume-title":"Algorithmic Learning for Knowledge-Based Systems","author":"Y Takada","year":"1995","unstructured":"Takada, Y.: Learning formal languages based on control sets. In: Jantke, K.P., Lange, S. (eds.) Algorithmic Learning for Knowledge-Based Systems. LNCS, vol. 961, pp. 316\u2013339. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60217-8_15"},{"key":"10_CR40","doi-asserted-by":"crossref","unstructured":"Yokomori, T.: Learning non-deterministic finite automata from queries and counterexamples. In: Machine Intelligence, vol. 13, pp. 169\u2013189 (1992)","DOI":"10.1093\/oso\/9780198538509.003.0007"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Image Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-23612-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,3]],"date-time":"2023-12-03T21:01:52Z","timestamp":1701637312000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-23612-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031236112","9783031236129"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-23612-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWCIA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Image Analysis","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Messina","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 July 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwcia2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iwcia2022.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"83% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}