{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:53:40Z","timestamp":1767855220556,"version":"3.49.0"},"reference-count":31,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,2,1]],"date-time":"2003-02-01T00:00:00Z","timestamp":1044057600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3855,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,2]]},"DOI":"10.1016\/s0304-3975(01)00349-8","type":"journal-article","created":{"date-parts":[[2003,1,21]],"date-time":"2003-01-21T14:54:09Z","timestamp":1043160849000},"page":"291-320","source":"Crossref","is-referenced-by-count":15,"title":["wMSO theories as grammar formalisms"],"prefix":"10.1016","volume":"293","author":[{"given":"James","family":"Rogers","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00349-8_BIB1","series-title":"29th IEEE International Symp. on Multiple-Valued Logic","first-page":"142","article-title":"Structural and behavioral modeling with monadic logics","author":"Ayari","year":"1999"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB2","doi-asserted-by":"crossref","unstructured":"D. Basin, N. Klarlund, Hardware verification using monadic second-order logic, in: Computer Aided Verification: 7th Internat. Conf., CAV\u201995, no. 939, Lecture Notes in Computer Science, Springer, Berlin, 1995.","DOI":"10.1007\/3-540-60045-0_38"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB3","unstructured":"T. Becker, HyTAG: a new type of tree adjoining grammars for hybrid syntactic representation of free word order languages, Ph.D. Thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 1993."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB4","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","article-title":"Weak second-order arithmetic and finite automata","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Z. Math. Logik Grundlagen der Math."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB5","doi-asserted-by":"crossref","unstructured":"M.-H. Candito, A principle-based hierarchical representation of LTAGs, in: 16th Internat. Conf. on Computational Linguistics, COLING\u201996, Copenhagen, Denmark, 1996.","DOI":"10.3115\/992628.992664"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB6","series-title":"Computer Programming and Formal Systems","first-page":"118","article-title":"The algebraic theory of context-free languages","author":"Chomsky","year":"1963"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB7","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","article-title":"Tree acceptors and some of their applications","volume":"4","author":"Doner","year":"1970","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","article-title":"Decision problems of finite automata design and related arithmetics","volume":"98","author":"Elgot","year":"1961","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB9","doi-asserted-by":"crossref","unstructured":"R. Evans, G. Gazdar, D. Weir, Encoding lexicalized tree adjoining grammars with a nonmonotonic inheritance hierarchy, in: 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, MA, 1995, pp. 77\u201384.","DOI":"10.3115\/981658.981669"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB10","series-title":"Handbook of Formal Languages: Beyond Words, Vol. 3","first-page":"1","article-title":"Tree languages","author":"G\u00e9cseg","year":"1997"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB11","unstructured":"S. Gorn, Processors for infinite codes of Shannon\u2013Fano type, in: Proceedings of the Symposium on Mathematical Theory of Automata, New York, April 1962, Brooklyn, N.Y: Polytechnic Press, 1963. Symp. Math. Theory of Automata, 1962."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB12","series-title":"Tools and Algorithms for the Construction and Analysis of Systems","first-page":"89","article-title":"MONA: monadic second-order logic in practice","author":"Henriksen","year":"1995"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB13","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0022-0000(75)80019-5","article-title":"Tree adjunct grammars","volume":"10","author":"Joshi","year":"1975","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB14","series-title":"Natural Language Processing: Psycholinguistic, Computational and Theoretical Perspectives","article-title":"How much context-sensitivity is required to provide reasonable structural descriptions: tree adjoining grammars","author":"Joshi","year":"1985"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB15","unstructured":"A.K. Joshi, Y. Schabes, Tree-adjoining grammars and lexicalized grammars, in: M. Nivat, A. Podelski (Eds.), Tree Automata and Languages, Elsevier Science Publishers B.V., Amsterdam, 1992, pp. 409\u2013431."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB16","series-title":"Tools and Algorithms for the Construction and Analysis of Systems","article-title":"MOSEL: a flexible toolset for monadic second-order logic","author":"Kelb","year":"1997"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB17","doi-asserted-by":"crossref","unstructured":"A.R. Meyer, Weak monadic second order theory of successor is not elementary-recursive, in: Proc. Logic Colloquium, no. 3 in Lecture Notes in Mathematics, Springer, Berlin, 1975, pp. 132\u2013154.","DOI":"10.1007\/BFb0064872"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB18","doi-asserted-by":"crossref","unstructured":"F. Morawietz, T. Cornell, Representing constraints with automata, in: Proc. of the 35th Annual Meeting of the Association for Computational Linguistics, Madrid, Spain, 1997, pp. 468\u2013475.","DOI":"10.3115\/976909.979677"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB19","doi-asserted-by":"crossref","unstructured":"F. Morawietz, T. Cornell, The MSO logic-automaton connection in linguistics, in: M. Moortgat (Ed.), Logical Aspects of Computational Linguistics, Springer, Berlin, 2001.","DOI":"10.1007\/3-540-48975-4_6"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB20","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB21","doi-asserted-by":"crossref","unstructured":"J. Rogers, A model-theoretic framework for theories of syntax, in: Proc. of the 34th Annual Meeting of the Association for Computational Linguistics, Santa Cruz, CA, 1996, pp. 10\u201316.","DOI":"10.3115\/981863.981865"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB22","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1023\/A:1005360201059","article-title":"\u201cGrammarless\u201d phrase structure grammar","volume":"20","author":"Rogers","year":"1997","journal-title":"Linguist. Philos."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB23","unstructured":"J. Rogers, A descriptive approach to language-theoretic complexity, Studies, Logic, Language Inform. CSLI\/FoLLI, 1998."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01695769","article-title":"Mappings and grammars on trees","volume":"4","author":"Rounds","year":"1970","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB25","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0022-0000(67)80022-9","article-title":"Characterizing derivation trees of context-free grammars through a generalization of finite automata theory","volume":"1","author":"Thatcher","year":"1967","journal-title":"J. Comput. and System Sci."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB26","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","article-title":"Generalized finite automata theory with an application to a decision problem of second-order logic","volume":"2","author":"Thatcher","year":"1968","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB27","series-title":"Unification-based Grammars","article-title":"Unification based tree adjoining grammars","author":"Vijay-Shanker","year":"1991"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB28","doi-asserted-by":"crossref","unstructured":"K. Vijay-Shanker, Y. Schabes, Structure sharing in lexicalized tree-adjoining grammars, in: Proceedings COLING\u201992, Nantes, France, 1992.","DOI":"10.3115\/992066.992100"},{"key":"10.1016\/S0304-3975(01)00349-8_BIB29","unstructured":"D.J. Weir, Characterizing mildly context-sensitive grammar formalisms, Ph.D. Thesis, University of Pennsylvania, 1988."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB30","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0304-3975(92)90124-X","article-title":"A geometric hierarchy beyond context-free languages","volume":"104","author":"Weir","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00349-8_BIB31","unstructured":"XTAG Research Group, A lexicalized tree adjoining grammar for English, Technical Report IRCS-98-18, Institute for Research in Cognitive Science, 1998."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003498?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003498?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,11]],"date-time":"2020-03-11T22:00:42Z","timestamp":1583964042000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003498"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,2]]}},"alternative-id":["S0304397501003498"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00349-8","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}