Constrained Expressions and their Derivatives

• Autorzy: Champarnaud J.-M. , Mignot L. , Nicart F.

Identyfikatory

DOI

10.3233/FI-2016-1451

• Języki publikacji: EN

Abstrakty

EN

This paper proposes an extension to classical regular expressions by the addition of two operators allowing the inclusion of boolean formulae from the zeroth order logic. These expressions are called constrained expressions. The associated language is defined thanks to the notion of interpretation and of realization. We show that the language associated when both interpretation and realization are fixed is stricly regular and can be not regular otherwise. Furthermore, we use an extension of Antimirov’s partial derivatives in order to solve the membership test in the general case. Finally, we show that once the interpretation is fixed, the membership test of a word in the language denoted by a constrained expression can be undecidable whereas it is always decidable when the interpretation is not fixed.

Słowa kluczowe

EN

expression derivatives; constrained expression; zeroth order logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 3
• Strony: 311--361
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Champarnaud J.-M.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Mignot L.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

autor

Nicart F.

• LITIS, Université de Rouen, 76801 Saint-Étienne du Rouvray Cedex, France

Bibliografia

• [1] Almeida R, Broda S, Moreira N. Deciding KAT and Hoare Logic with Derivatives, GandALF (M. Faella, A. Murano, Eds.), 2012;96:127–140. doi:10.4204/EPTCS.96.10.
• [2] Antimirov V. Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci., 1996;155(2):291–319. doi:10.1016/0304-3975(95)00182-4.
• [3] Brzozowski JA. Derivatives of regular expressions, J. Assoc. Comput. Mach., 1964;11(4):481–494. doi:10.1145/321239.321249.
• [4] Brzozowski JA. Regular-Like Expressions for Some Irregular Languages, SWAT (FOCS), IEEE Computer Society, 1968, p. 278–286. doi:10.1109/SWAT.1968.24.
• [5] Câmpeanu C, Salomaa K, Yu S. A Formal Study Of Practical Regular Expressions, Int. J. Found. Comput. Sci., 2003;14(6):1007–1018. Available from: http://dx.doi.org/10.1142/S012905410300214X.
• [6] Caron P, Champarnaud J, Migno L. A general framework for the derivation of regular expressions, RAIRO - Theor. Inf. and Applic., 2014;48(3):281–305. Available from: http://dx.doi.org/10.1051/ita/2014010.
• [7] Caron P, Champarnaud JM, Mignot L. Partial Derivatives of an Extended Regular Expression, LATA (A. H. Dediu, S. Inenaga, C. Martín-Vide, Eds.), 6638, Springer, 2011, ISBN:978-3-642-21253-6.
• [8] Caron P, Champarnaud JM, Mignot L. Multi-Tilde-Bar Derivatives, CIAA (N. Moreira, R. Reis, Eds.), 7381, Springer, 2012, p. 321–328. ISBN:978-3-642-31605-0. doi:10.1007/978-3-642-31606-7_28.
• [9] Champarnaud JM, Dubernard JP, Jeanne H, Mignot L. Two-Sided Derivatives for Regular Expressions and for Hairpin Expressions, LATA (A. H. Dediu, C. Martín-Vide, B. Truthe, Eds.), 7810, Springer, 2013, p. 202–213. ISBN:978-3-642-37063-2.
• [10] Champarnaud JM, Jeanne H, Mignot L. Derivatives of Approximate Regular Expressions, Discrete Mathematics & Theoretical Computer Science, 2013;15(2):95–120. arXiv:1205.1825v3.
• [11] Chomsky N. Three models for the description of language, IRE Trans. on Information Theory, 1956;2(3):113–124. doi:10.1109/TIT.1956.1056813.
• [12] Glushkov VM. On a synthesis algorithm for abstract automata, Ukr. Matem. Zhurnal, 1960;12(2):147–156, In Russian. doi:10.1007/BF02531491.
• [13] Gruber H, Holzer M. From Finite Automata to Regular Expressions and Back–A Summary on Descriptional Complexity, EPTCS: AFL14, 2014;51:25–48. doi:10.4204/EPTCS.151.2.
• [14] Ilie L, Yu S. Follow automata., Inf. Comput., 2003;186(1):140–162. doi:10.1016/S0890-5401(03)00090-7.
• [15] Matiyasevich YV. Hilbert’s Tenth Problem, MIT Press Series in the Foundations of Computing, MIT Press, Cambridge, Massachusetts, 1993. With a foreword by Martin Davis. ISBN:0-262-13295-8.
• [16] McNaughton RF, Yamada H. Regular Expressions and State Graphs for Automata, IEEE Transactions on Electronic Computers, 1960;9(1):39–57. doi:10.1109/TEC.1960.5221603.
• [17] Might M, Darais D, Spiewak D. Parsing with derivatives: a functional pearl, ICFP (M. M. T. Chakravarty, Z. Hu, O. Danvy, Eds.), ACM, 2011, ISBN:978-1-4503-0865-6. doi:10.1145/2034773.2034801.
• [18] Sempere JM. On a Class of Regular-like Expressions for Linear Languages, Journal of Automata, Languages and Combinatorics, 2000;5(3):343–354. Available from: http://dl.acm.org/citation.cfm?id=350226.350251.
• [19] Skolem T. The foundations of elementary arithmetic established by means of the recursive mode of thought, without the use of apparent variables ranging over infinite domains, In: Heijenoort, J.v. (eds) From Frege to GÃűdel, Harvard, Iuniverse 1967, p. 302–333.
• [20] Sulzmann M, Lu KZM. Regular expression sub-matching using partial derivatives, Principles and Practice of Declarative Programming, PPDP’12, Leuven, Belgium - September 19 - 21, 2012, (D. D. Schreye, G. Janssens, A. King, Eds.), ACM, 2012, p. 79–90. doi:10.1145/2370776.2370788.
• [21] Thompson K. Regular expression search algorithm, Comm. ACM, 1968;11(6):419–422. doi:10.1145/363347.363387.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).