{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T02:04:19Z","timestamp":1776305059449,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540280057","type":"print"},{"value":"9783540318644","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11532231_25","type":"book-chapter","created":{"date-parts":[[2010,7,21]],"date-time":"2010-07-21T18:56:52Z","timestamp":1279738612000},"page":"337-352","source":"Crossref","is-referenced-by-count":67,"title":["On the Complexity of Equational Horn Clauses"],"prefix":"10.1007","author":[{"given":"Kumar Neeraj","family":"Verma","sequence":"first","affiliation":[]},{"given":"Helmut","family":"Seidl","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","first-page":"82","volume-title":"CSFW 2001","author":"B. Blanchet","year":"2001","unstructured":"Blanchet, B.: An efficient cryptographic protocol verifier based on Prolog rules. In: CSFW 2001, pp. 82\u201396. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Chevalier, Y., K\u00fcsters, R., Rusinowitch, M., Turuani, M.: An NP decision procedure for protocol insecurity with XOR. In: LICS 2003, pp. 261\u2013270 (2003)","DOI":"10.1109\/LICS.2003.1210066"},{"key":"25_CR3","volume-title":"Electronic Notes in Theoretical Computer Science","author":"T. Colcombet","year":"2002","unstructured":"Colcombet, T.: Rewriting in the partial algebra of typed terms modulo AC. In: Electronic Notes in Theoretical Computer Science, vol.\u00a068, Elsevier Science Publishers, Amsterdam (2002)"},{"key":"25_CR4","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (1997), http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-44881-0_12","volume-title":"Rewriting Techniques and Applications","author":"H. Comon-Lundh","year":"2003","unstructured":"Comon-Lundh, H., Cortier, V.: New decidability results for fragments of first-order logic and application to cryptographic protocols. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 148\u2013164. Springer, Heidelberg (2003)"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Cortier, V., Delaune, S., Lafourcade, P.: A survey of algebraic properties used in cryptographic protocols. Journal of Computer Security (2005) (To appear)","DOI":"10.3233\/JCS-2006-14101"},{"key":"25_CR7","first-page":"64","volume-title":"LICS 2004","author":"P. Groote de","year":"2004","unstructured":"de Groote, P., Guillaume, B., Salvati, S.: Vector addition tree automata. In: LICS 2004, pp. 64\u201373. IEEE Computer Society Press, Los Alamitos (2004)"},{"issue":"1","key":"25_CR8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.3233\/FI-1997-3112","volume":"31","author":"J. Esparza","year":"1997","unstructured":"Esparza, J.: Petri nets, commutative context-free grammars, and basic parallel processes. Fundam. Inform.\u00a031(1), 13\u201325 (1997)","journal-title":"Fundam. Inform."},{"issue":"2","key":"25_CR9","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Semigroups, Presburger formulas and languages. Pacific Journal of Mathematic\u00a016(2), 285\u2013296 (1966)","journal-title":"Pacific Journal of Mathematic"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-540-30579-8_24","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"J. Goubault-Larrecq","year":"2005","unstructured":"Goubault-Larrecq, J., Parrennes, F.: Cryptographic protocol analysis on real C code. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol.\u00a03385, pp. 363\u2013379. Springer, Heidelberg (2005)"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Goubault-Larrecq, J., Roger, M., Verma, K.N.: Abstraction and resolution modulo AC: How to verify Diffie-Hellman-like protocols automatically. Journal of Logic and Algebraic Programming (2005) (to appear), Available as Research Report LSV-04-7, LSV, ENS Cachan","DOI":"10.1016\/j.jlap.2004.09.004"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/3-540-36576-1_21","volume-title":"Foundations of Software Science and Computational Structures","author":"D. Lugiez","year":"2003","unstructured":"Lugiez, D.: Counting and equality constraints for multitree automata. In: Gordon, A.D. (ed.) FOSSACS 2003. LNCS, vol.\u00a02620, pp. 328\u2013342. Springer, Heidelberg (2003)"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/3-540-45789-5_5","volume-title":"Static Analysis","author":"F. Nielson","year":"2002","unstructured":"Nielson, F., Riis Nielson, H., Seidl, H.: Normalizable horn clauses, strongly recognizable relations, and spi. In: Hermenegildo, M.V., Puebla, G. (eds.) SAS 2002. LNCS, vol.\u00a02477, pp. 20\u201335. Springer, Heidelberg (2002)"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-45610-4_9","volume-title":"Rewriting Techniques and Applications","author":"H. Ohsaki","year":"2002","unstructured":"Ohsaki, H., Takai, T.: Decidability and closure properties of equational tree languages. In: Tison, S. (ed.) RTA 2002. LNCS, vol.\u00a02378, pp. 114\u2013128. Springer, Heidelberg (2002)"},{"issue":"4","key":"25_CR15","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R.J. Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. Journal of the ACM\u00a013(4), 570\u2013581 (1966)","journal-title":"Journal of the ACM"},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01270929","volume":"6","author":"M. Rusinowitch","year":"1995","unstructured":"Rusinowitch, M., Vigneron, L.: Automated deduction with associative-commutative operators. Applicable Algebra in Engineering, Communication and Computation\u00a06, 23\u201356 (1995)","journal-title":"Applicable Algebra in Engineering, Communication and Computation"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Seidl, H., Schwentick, T., Muscholl, A.: Numerical document queries. In: PODS 2003, pp. 155\u2013166 (2003)","DOI":"10.1145\/773153.773169"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1007\/978-3-540-27836-8_94","volume-title":"Automata, Languages and Programming","author":"H. Seidl","year":"2004","unstructured":"Seidl, H., Schwentick, T., Muscholl, A., Habermehl, P.: Counting in trees for free. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1136\u20131149. Springer, Heidelberg (2004)"},{"key":"25_CR19","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-540-32275-7_6","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"H. Seidl","year":"2005","unstructured":"Seidl, H., Verma, K.N.: Flat and one-variable clauses: Complexity of verifying cryptographic protocols with single blind copying. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 79\u201394. Springer, Heidelberg (2005)"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/3-540-44881-0_14","volume-title":"Rewriting Techniques and Applications","author":"K.N. Verma","year":"2003","unstructured":"Verma, K.N.: Two-way equational tree automata for AC-like theories: Decidability and closure properties. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 180\u2013196. Springer, Heidelberg (2003)"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1007\/978-3-540-30538-5_43","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"K.N. Verma","year":"2004","unstructured":"Verma, K.N.: Alternation in equational tree automata modulo XOR. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 518\u2013530. Springer, Heidelberg (2004)"},{"key":"25_CR22","doi-asserted-by":"crossref","unstructured":"Verma, K.N., Goubault-Larrecq, J.: Karp-Miller trees for a branching extension of VASS. Research Report LSV-04-3, LSV, ENS Cachan, France (January 2004)","DOI":"10.46298\/dmtcs.350"}],"container-title":["Lecture Notes in Computer Science","Automated Deduction \u2013 CADE-20"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11532231_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T06:05:07Z","timestamp":1740290707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11532231_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280057","9783540318644"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11532231_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}