{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T11:49:32Z","timestamp":1783684172122,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540368342","type":"print"},{"value":"9783540368359","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11805618_5","type":"book-chapter","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:29:13Z","timestamp":1153837753000},"page":"50-65","source":"Crossref","is-referenced-by-count":9,"title":["Propositional Tree Automata"],"prefix":"10.1007","author":[{"given":"Joe","family":"Hendrix","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hitoshi","family":"Ohsaki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahesh","family":"Viswanathan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","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. Information and Computation\u00a075, 87\u2013106 (1987)","journal-title":"Information and Computation"},{"key":"5_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/11513988_27","volume-title":"Computer Aided Verification","author":"A. Armando","year":"2005","unstructured":"Armando, A., Basin, D., Boichut, Y., Chevalier, Y., Compagna, L., Cuellar, J., Hankes Drielsma, P., He\u00e1m, P.-C., Kouchnarenko, O., Mantovani, J., M\u00f6dersheim, S., von Oheimb, D., Rusinowitch, M., Santiago, J., Turuani, M., Vigan\u00f2, L., Vigneron, L.: The AVISPA Tool for the Automated Validation of Internet Security Protocols and Applications. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol.\u00a03576, pp. 281\u2013285. Springer, Heidelberg (2005)"},{"key":"5_CR3","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Context-Free Languages and Push-Down Automata, Handbook of Formal Languages","author":"J. Autebert","year":"1997","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-Free Languages and Push-Down Automata, Handbook of Formal Languages, vol.\u00a01, pp. 111\u2013174. Springer, Heidelberg (1997)"},{"key":"5_CR4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172752","volume-title":"Term Rewriting and All That","author":"F. Baader","year":"1998","unstructured":"Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)"},{"key":"5_CR5","unstructured":"Boichut, Y., He\u00e1m, P.-C., Kouchnarenko, O.: Automatic Verification of Security Protocols Using Approximations, technical report RR-5727, INRIA (October 2005)"},{"key":"5_CR6","series-title":"TCS","first-page":"35","volume-title":"Specification and Proof in Membership Equational Logic","author":"A. Bouhoula","year":"2000","unstructured":"Bouhoula, A., Jouannaud, J.P., Meseguer, J.: Specification and Proof in Membership Equational Logic. TCS, vol.\u00a0236, pp. 35\u2013132. Elsevier, Amsterdam (2000)"},{"key":"5_CR7","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications, incomplete draft (2005), available at: http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BFb0032738","volume-title":"Static Analysis","author":"P. Devienne","year":"1997","unstructured":"Devienne, P., Talbot, J.-M., Tison, S.: Set-Based Analysis for Logic Programming and Tree Automata. In: Van Hentenryck, P. (ed.) SAS 1997. LNCS, vol.\u00a01302, pp. 127\u2013140. Springer, Heidelberg (1997)"},{"key":"5_CR9","volume-title":"Theory of Computational Complexity","author":"D.-Z. Du","year":"2000","unstructured":"Du, D.-Z., Ko, K.: Theory of Computational Complexity. John Wiley and Sons, Chichester (2000)"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/3-540-45587-6_16","volume-title":"Practical Aspects of Declarative Languages","author":"J.P. Gallagher","year":"2002","unstructured":"Gallagher, J.P., Puebla, G.: Abstract Interpretation over Non-deterministic Finite Tree Automata for Set-Based Analysis of Logic Programs. In: Krishnamurthi, S., Ramakrishnan, C.R. (eds.) PADL 2002. LNCS, vol.\u00a02257, pp. 243\u2013261. Springer, Heidelberg (2002)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/10721959_21","volume-title":"Automated Deduction - CADE-17","author":"T. Genet","year":"2000","unstructured":"Genet, T., Klay, F.: Rewriting for Cryptographic Protocol Verification. In: McAllester, D. (ed.) CADE 2000. LNCS, vol.\u00a01831, pp. 271\u2013290. Springer, Heidelberg (2000)"},{"key":"5_CR12","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York (1966)"},{"key":"5_CR13","unstructured":"Hendrix, J., Ohsaki, H., Meseguer, J.: Sufficient Completeness Checking with Propositional Tree Automata, technical report UIUCDCS-R-2005-2635, Department of Computer Science, University of Illinois at Urbana-Champaign (2005), available at: http:\/\/texas.cs.uiuc.edu\/"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Hendrix, J., Ohsaki, H., Viswanathan, M.: Propositional Tree Automat, technical report UIUCDCS-R-2006-2695, University of Illinios at Urbana-Champaign (2005), available at: http:\/\/texas.cs.uiuc.edu\/","DOI":"10.1007\/11805618_5"},{"key":"5_CR15","unstructured":"Hendrix, J.: CETA: A Library for Equational Tree Automata, Department of Computer Science, University of Illinois at Urbana-Champaign (2006), Software available under GPL license at: http:\/\/texas.cs.uiuc.edu\/ceta\/"},{"key":"5_CR16","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Reading (1979)"},{"key":"5_CR17","first-page":"11","volume-title":"Proc. of 5th ICFP, SIGPLAN","author":"H. Hosoya","year":"2000","unstructured":"Hosoya, H., Vouillon, J., Pierce, B.C.: Regular Expression Types for XML. In: Proc. of 5th ICFP, SIGPLAN, Montreal (Canada), vol.\u00a035(9), pp. 11\u201322. ACM, New York (2000)"},{"key":"5_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. MIT Press, Cambridge (1994)"},{"key":"5_CR19","unstructured":"Klarlund, N., M\u00f8ller, A.: MONA Version 1.4 User Manual, BRICS Notes Series NS-01-1, Department of Computer Science, University of Aarhus (2001)"},{"key":"5_CR20","series-title":"TCS","volume-title":"Multitree Automata That Count","author":"D. Lugiez","year":"2005","unstructured":"Lugiez, D.: Multitree Automata That Count. TCS, vol.\u00a0333. Elsevier, Amsterdam (2005)"},{"issue":"1","key":"5_CR21","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1162\/089120100561610","volume":"26","author":"M. Nederhof","year":"2000","unstructured":"Nederhof, M.: Practical Experiments with Regular Approximation of Context-Free Languages. Computational Linguistics\u00a026(1), 17\u201344 (2000)","journal-title":"Computational Linguistics"},{"key":"5_CR22","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/11591191_24","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"H. Ohsaki","year":"2005","unstructured":"Ohsaki, H., Talbot, J.-M., Tison, S., Roos, Y.: Monotone AC-Tree Automata. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS (LNAI), vol.\u00a03835, pp. 337\u2013351. Springer, Heidelberg (2005)"},{"key":"5_CR23","series-title":"ENTCS","first-page":"97","volume-title":"Proc. of 5th RULE","author":"H. Ohsaki","year":"2005","unstructured":"Ohsaki, H., Takai, T.: ACTAS: A System Design for Associative and Commutative Tree Automata Theory. In: Proc. of 5th RULE, Aachen (Germany). ENTCS, vol.\u00a0124, pp. 97\u2013111. Elsevier, Amsterdam (2005)"},{"key":"5_CR24","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)"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/3-540-44802-0_38","volume-title":"Computer Science Logic","author":"H. Ohsaki","year":"2001","unstructured":"Ohsaki, H.: Beyond Regularity: Equational Tree Automata for Associative and Commutative Theories. In: Fribourg, L. (ed.) CSL 2001 and EACSL 2001. LNCS, vol.\u00a02142, pp. 539\u2013553. Springer, Heidelberg (2001)"},{"issue":"4","key":"5_CR26","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R. Parikh","year":"1966","unstructured":"Parikh, R.: On Context-Free Languages. JACM\u00a013(4), 570\u2013581 (1966)","journal-title":"JACM"},{"key":"5_CR27","first-page":"155","volume-title":"Proc. of 22nd PODS","author":"H. Seidl","year":"2003","unstructured":"Seidl, H., Schwentick, T., Muscholl, A.: Numerical Document Queries. In: Proc. of 22nd PODS, SanDiego (USA), pp. 155\u2013166. ACM, New York (2003)"},{"key":"5_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/11562948_19","volume-title":"Automated Technology for Verification and Analysis","author":"I. Yagi","year":"2005","unstructured":"Yagi, I., Takata, Y., Seki, H.: A Static Analysis Using Tree Automata for XML Access Control. In: Peled, D.A., Tsay, Y.-K. (eds.) ATVA 2005. LNCS, vol.\u00a03707, pp. 234\u2013247. Springer, Heidelberg (2005)"},{"key":"5_CR29","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\u2013197. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Term Rewriting and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11805618_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:12:49Z","timestamp":1605643969000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11805618_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540368342","9783540368359"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11805618_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}