{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:04:08Z","timestamp":1743037448990,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319948119"},{"type":"electronic","value":"9783319948126"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94812-6_2","type":"book-chapter","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T22:12:26Z","timestamp":1530223946000},"page":"4-27","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Regular Expressions and Transducers over Alphabet-Invariant and User-Defined Labels"],"prefix":"10.1007","author":[{"given":"Stavros","family":"Konstantinidis","sequence":"first","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]},{"given":"Joshua","family":"Young","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"issue":"2","key":"2_CR1","first-page":"117","volume":"8","author":"C Allauzen","year":"2003","unstructured":"Allauzen, C., Mohri, M.: Efficient algorithms for testing the twins property. J. Autom. Lang. Comb. 8(2), 117\u2013144 (2003)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2","key":"2_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"VM Antimirov","year":"1996","unstructured":"Antimirov, V.M.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155(2), 291\u2013319 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"2_CR3","first-page":"5","volume":"22","author":"R Bastos","year":"2017","unstructured":"Bastos, R., Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average complexity of partial derivative automata for semi-extended expressions. J. Autom. Lang. Comb. 22(1\u20133), 5\u201328 (2017)","journal-title":"J. Autom. Lang. Comb."},{"issue":"1","key":"2_CR4","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(01)00214-6","volume":"292","author":"M-P B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.-P., Carton, O., Prieur, C., Sakarovitch, J.: Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci. 292(1), 45\u201363 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"2_CR5","doi-asserted-by":"publisher","first-page":"1593","DOI":"10.1142\/S0129054111008908","volume":"22","author":"S Broda","year":"2011","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On the average state complexity of partial derivative automata: an analytic combinatorics approach. Int. J. Found. Comput. Sci. 22(7), 1593\u20131606 (2011). MR2865339","journal-title":"Int. J. Found. Comput. Sci."},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1109\/PGEC.1963.263416","volume":"12","author":"JA Brzozowski","year":"1963","unstructured":"Brzozowski, J.A., McCluskey, E.J.: Signal flow graph techniques for sequential circuit state diagrams. IEEE Trans. Electron. Comput. 12, 67\u201376 (1963)","journal-title":"IEEE Trans. Electron. Comput."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J Brzozowski","year":"1964","unstructured":"Brzozowski, J.: Derivatives of regular expressions. J. Assoc. Comput. Mach. 11, 481\u2013494 (1964)","journal-title":"J. Assoc. Comput. Mach."},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-642-21254-3_13","volume-title":"Language and Automata Theory and Applications","author":"P Caron","year":"2011","unstructured":"Caron, P., Champarnaud, J.-M., Mignot, L.: Partial derivatives of an extended regular expression. In: Dediu, A.-H., Inenaga, S., Mart\u00edn-Vide, C. (eds.) LATA 2011. LNCS, vol. 6638, pp. 179\u2013191. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21254-3_13"},{"issue":"3","key":"2_CR9","first-page":"195","volume":"45","author":"JM Champarnaud","year":"2001","unstructured":"Champarnaud, J.M., Ziadi, D.: From Mirkin\u2019s prebases to Antimirov\u2019s word partial derivatives. Fundam. Inf. 45(3), 195\u2013205 (2001)","journal-title":"Fundam. Inf."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0304-3975(01)00267-5","volume":"289","author":"JM Champarnaud","year":"2002","unstructured":"Champarnaud, J.M., Ziadi, D.: Canonical derivatives, partial derivatives and finite automaton constructions. Theor. Comput. Sci. 289, 137\u2013163 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-319-40946-7_5","volume-title":"Implementation and Application of Automata","author":"A Demaille","year":"2016","unstructured":"Demaille, A.: Derived-term automata of multitape rational expressions. In: Han, Y.-S., Salomaa, K. (eds.) CIAA 2016. LNCS, vol. 9705, pp. 51\u201363. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-40946-7_5"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-319-08846-4_12","volume-title":"Implementation and Application of Automata","author":"A Demaille","year":"2014","unstructured":"Demaille, A., Duret-Lutz, A., Lombardy, S., Saiu, L., Sakarovitch, J.: A type system for weighted automata and rational expressions. In: Holzer, M., Kutrib, M. (eds.) CIAA 2014. LNCS, vol. 8587, pp. 162\u2013175. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08846-4_12"},{"key":"2_CR13","unstructured":"FAdo: Tools for formal languages manipulation. http:\/\/fado.dcc.fc.up.pt\/. Accessed Apr 2018"},{"key":"2_CR14","first-page":"278","volume":"8","author":"S Konstantinidis","year":"2002","unstructured":"Konstantinidis, S.: Transducers and the properties of error-detection, error-correction and finite-delay decodability. J. Univ. Comput. Sci. 8, 278\u2013291 (2002)","journal-title":"J. Univ. Comput. Sci."},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-319-60252-3_4","volume-title":"Descriptional Complexity of Formal Systems","author":"S Konstantinidis","year":"2017","unstructured":"Konstantinidis, S.: Applications of transducers in independent languages, word distances, codes. In: Pighizzini, G., C\u00e2mpeanu, C. (eds.) DCFS 2017. LNCS, vol. 10316, pp. 45\u201362. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-60252-3_4"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Konstantinidis, S. Moreira, N., Reis, R., Young, J.: Regular expressions and transducers over alphabet-invariant and user-defined labels. $${{\\rm {arXiv}}{.}\\text{org}}$$, arXiv:1805.01829 (2018)","DOI":"10.1007\/978-3-319-94812-6_2"},{"issue":"1\u20133","key":"2_CR17","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.tcs.2004.10.016","volume":"332","author":"S Lombardy","year":"2005","unstructured":"Lombardy, S., Sakarovitch, J.: Derivatives of rational expressions with multiplicity. Theor. Comput. Sci. 332(1\u20133), 141\u2013177 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR18","first-page":"51","volume":"5","author":"BG Mirkin","year":"1966","unstructured":"Mirkin, B.G.: An algorithm for constructing a base in a language of regular expressions. Eng. Cybern. 5, 51\u201357 (1966)","journal-title":"Eng. Cybern."},{"key":"2_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139195218","volume-title":"Elements of Automata Theory","author":"J Sakarovitch","year":"2009","unstructured":"Sakarovitch, J.: Elements of Automata Theory. Cambridge University Press, Berlin (2009)"},{"key":"2_CR20","unstructured":"Sakarovitch, J.: Automata and rational expressions. $${\\rm arXiv.}{\\rm org}$$, arXiv:1502.03573 (2015)"},{"key":"2_CR21","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BFb0087133","volume-title":"S\u00e9minaire d\u2019Alg\u00e8bre Paul Dubreil Paris 1975\u20131976 (29\u00e8me Ann\u00e9e)","author":"HJ Shyr","year":"1977","unstructured":"Shyr, H.J., Thierrin, G.: Codes and binary relations. In: Malliavin, M.P. (ed.) S\u00e9minaire d\u2019Alg\u00e8bre Paul Dubreil Paris 1975\u20131976 (29\u00e8me Ann\u00e9e). LNM, vol. 586, pp. 180\u2013188. Springer, Heidelberg (1977). https:\/\/doi.org\/10.1007\/BFb0087133"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Regular expression search algorithm. Commun. ACM (CACM) 11, 419\u2013422 (1968)","journal-title":"Commun. ACM (CACM)"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-39274-0_3","volume-title":"Implementation and Application of Automata","author":"M Veanes","year":"2013","unstructured":"Veanes, M.: Applications of symbolic finite automata. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 16\u201323. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39274-0_3"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Veanes, M., Hooimeijer, P., Livshits, B., Molnar, D., Bjorner, N.: Symbolic finite state transducers: algorithms and applications. In: Field, J., Hicks, M. (eds.) Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, pp. 137\u2013150 (2012)","DOI":"10.1145\/2103656.2103674"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"Y Sheng","year":"1997","unstructured":"Sheng, Y.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. I, pp. 41\u2013110. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94812-6_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:45:02Z","timestamp":1709826302000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94812-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319948119","9783319948126"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94812-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Charlottetown, PE","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.smcs.upei.ca\/ciaa2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}