{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:25:50Z","timestamp":1761611150187},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Logic Lang Inf"],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/bf01050635","type":"journal-article","created":{"date-parts":[[2005,1,27]],"date-time":"2005-01-27T14:50:36Z","timestamp":1106837436000},"page":"129-169","source":"Crossref","is-referenced-by-count":37,"title":["A modal perspective on the computational complexity of attribute value grammar"],"prefix":"10.1007","volume":"2","author":[{"given":"Patrick","family":"Blackburn","sequence":"first","affiliation":[]},{"given":"Edith","family":"Spaan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","volume-title":"EATCS Monographs on Theoretical Computer Science 11","author":"J. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J., D\u00edaz, J. and Gabarr\u00f3, J., 1988,Structural Complexity I, EATCS Monographs on Theoretical Computer Science 11, Berlin: Springer Verlag."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1016\/0022-0000(82)90018-6","volume":"25","author":"M. Ben-Ari","year":"1982","unstructured":"Ben-Ari, M., Halpern, J. and Pnueli, A., 1982, ?Deterministic propositional dynamic logic: finite models, complexity and completeness?,Journal of Computer and System Sciences 25, 402?417.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR3","first-page":"1","volume":"66","author":"R. Berger","year":"1966","unstructured":"Berger, R., 1966, ?The undecidability of the dominoe problem?,Mem. Amer. Math. Soc. 66, 1?72.","journal-title":"Mem. Amer. Math. Soc."},{"key":"CR4","unstructured":"Blackburn, P., 1989, ?Nominal tense logic?, to appear inNotre Dame Journal of Formal Logic."},{"key":"CR5","series-title":"Studies in Logic, Language and Information","volume-title":"Diamonds and Defaults","author":"P. Blackburn","year":"1991","unstructured":"Blackburn, P., 1991, ?Modal logic and attribute value structures?, to appear inDiamonds and Defaults, M. de Rijke, ed., Studies in Logic, Language and Information, Dordrecht: Kluwer."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0898-1221(92)90146-9","volume":"23","author":"C. Brink","year":"1992","unstructured":"Brink, C. and Schmidt, R., 1992, ?Subsumption computed algebraically?,Computers Math. Applic. 23, 329?342.","journal-title":"Computers Math. Applic."},{"key":"CR7","first-page":"171","volume":"12","author":"R. Bull","year":"1970","unstructured":"Bull, R., 1970, ?An approach to tense logic?,Theoria 12, 171?182.","journal-title":"Theoria"},{"key":"CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511530098","volume-title":"The Logic of Typed Feature Structures","author":"B. Carpenter","year":"1992","unstructured":"Carpenter, B., 1992,The Logic of Typed Feature Structures, Cambridge: Cambridge University Press."},{"key":"CR9","volume-title":"Categories, Polymorphism and Unification","author":"R. Evans","year":"1987","unstructured":"Evans, R., 1987, ?Towards a formal specification for defaults in GPSG?, inCategories, Polymorphism and Unification, E. Klein and J. van Benthem, eds., Edinburgh: Centre for Cognitive Science and Amsterdam: ITLI."},{"key":"CR10","volume-title":"AISB-89, Proceedings of the Seventh Conference of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour","author":"R. Evans","year":"1989","unstructured":"Evans, R. and Gazdar, G., 1989, ?The semantics of DATR?,AISB-89, Proceedings of the Seventh Conference of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour, A. Cohn, ed., London: Pitman."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/0022-0000(79)90046-1","volume":"18","author":"M. Fischer","year":"1979","unstructured":"Fischer, M. and Ladner, R., 1979, ?Propositional dynamic logic of regular programs?,Journal of Computer and System Sciences 18, 194?211.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR12","volume-title":"in Mathematical Logic and its Applications. Proceedings of the 1986 G\u00f6del Summer School and Conference Bulgaria","author":"G. Gargov","year":"1986","unstructured":"Gargov, G., Passy, S. and Tinchev, T., 1986, ?Modal environment for boolean speculations (preliminary report)?, inin Mathematical Logic and its Applications. Proceedings of the 1986 G\u00f6del Summer School and Conference Bulgaria, D. Skordev, ed., New York: Plenum Press."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0304-3975(88)90126-0","volume":"61","author":"G. Gargov","year":"1988","unstructured":"Gargov, G. and Passy, S., 1988, ?Determinism and looping in combinatory PDL?,Theoretical Computer Science 61, pages 259?277.","journal-title":"Theoretical Computer Science"},{"key":"CR14","unstructured":"Gargov, G. and Goranko, V., 1989, ?Modal logic with names?, to appear inJournal of Philosophical Logic."},{"key":"CR15","volume-title":"Generalized Phrase Structure Grammar","author":"G. Gazdar","year":"1985","unstructured":"Gazdar, G., Klein, E., Pullum, G. and Sag, I., 1985,Generalized Phrase Structure Grammar, Oxford: Basil Blackwell."},{"key":"CR16","first-page":"1","volume":"14","author":"G. Gazdar","year":"1988","unstructured":"Gazdar, G., Pullum G., Carpenter, R., Klein, E., Hukari, T. and Levine, R., 1988, ?Category structures?,Computational Linguistics 14, pages 1?19.","journal-title":"Computational Linguistics"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0168-0072(89)90032-8","volume":"44","author":"R. Goldblatt","year":"1989","unstructured":"Goldblatt, R., 1989, ?Varieties of complex algebras?,Annals of Pure and Applied Logic 44, 173?242.","journal-title":"Annals of Pure and Applied Logic"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/logcom\/2.1.5","volume":"2","author":"V. Goranko","year":"1992","unstructured":"Goranko, V. and Passy, S., 1992, ?Using the universal modality: gains and questions?,Journal of Logic and Computation 2, 5?30.","journal-title":"Journal of Logic and Computation"},{"key":"CR19","unstructured":"Halpern, J. and Moses, M., 1985, ?A guide to the modal logics of knowledge and belief?, pp. 480?490 inProceedings 9th International Joint Conference on Artificial Intelligence."},{"key":"CR20","doi-asserted-by":"crossref","unstructured":"Harel, D., 1983, ?Recurring dominoes: making the highly undecidable highly understandable?, pp. 177?194 inProc. of the Conference on Foundations of Computing Theory, Springer Lecture Notes in Computer Science158.","DOI":"10.1007\/3-540-12689-9_103"},{"key":"CR21","volume-title":"Handbook of Philosophical Logic 2","author":"D. Harel","year":"1984","unstructured":"Harel, D., 1984, ?Dynamic logic?, inHandbook of Philosophical Logic 2, D. Gabbay and F. Guenthner, eds., Dordrecht: Reidel."},{"issue":"1","key":"CR22","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/4904.4993","volume":"33","author":"D. Harel","year":"1986","unstructured":"Harel, D., 1986, ?Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness?,Journal of the ACM 33(1), 224?248.","journal-title":"Journal of the ACM"},{"key":"CR23","unstructured":"van der Hoek, W. and de Rijke, M., 1991, ?Generalized quantifiers and modal logic?, to appear inJournal of Logic, Language and Information."},{"key":"CR24","volume-title":"A Companion to Modal Logic","author":"G. Hughes","year":"1984","unstructured":"Hughes, G. and Cresswell, M., 1984,A Companion to Modal Logic, London: Methuen & Co. Ltd."},{"key":"CR25","first-page":"173","volume-title":"The Mental Representation of Grammatical Relations","author":"K. Kaplan","year":"1982","unstructured":"Kaplan, K. and Bresnan, J., 1982, ?Lexical functional grammar: a formal system for grammatical representation?, pp. 173?281 inThe Mental Representation of Grammatical Relations, Joan Bresnan, ed., Cambridge: MIT Press."},{"key":"CR26","first-page":"28","volume-title":"Proceedings of the 10th International Conference on Computational Linguistics and the 22nd Annual Meeting of the Association for Computational Linguistics","author":"L. Karttunen","year":"1984","unstructured":"Karttunen, L., 1984, ?Features and values?, pp. 28?33 inProceedings of the 10th International Conference on Computational Linguistics and the 22nd Annual Meeting of the Association for Computational Linguistics, Stanford, California."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"257","DOI":"10.3115\/981131.981166","volume-title":"Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics","author":"R. Kasper","year":"1986","unstructured":"Kasper, R. and Rounds, W., 1986, ?A logical semantics for feature structures?, pp. 257?266 inProceedings of the 24th Annual Meeting of the Association for Computational Linguistics, Columbia University, New York."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF00630516","volume":"13","author":"R. Kasper","year":"1990","unstructured":"Kasper, R. and Rounds, W., 1990, ?The logic of unification in grammar?,Linguistics and Philosophy 13, 33?58.","journal-title":"Linguistics and Philosophy"},{"key":"CR29","series-title":"School of Cognitive and Computing Sciences","volume-title":"PhD thesis","author":"B. Keller","year":"1991","unstructured":"Keller, B., 1991,Feature Logics, Infinitary Descriptions and the Logical Treatment of Grammar, PhD thesis, School of Cognitive and Computing Sciences, University of Sussex, United Kingdom."},{"key":"CR30","first-page":"111","volume":"15","author":"M. Kracht","year":"1989","unstructured":"Kracht, M., 1989, ?On the logic of category definition?,Computational Linguistics 15, 111?113.","journal-title":"Computational Linguistics"},{"issue":"3","key":"CR31","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0206033","volume":"6","author":"R. Ladner","year":"1977","unstructured":"Ladner, R., 1977, ?The computational complexity of provability in systems of modal logic?,SIAM Journal on Computing 6(3), 467?480.","journal-title":"SIAM Journal on Computing"},{"key":"CR32","volume-title":"Proceedings of the MSRI Workshop on Logic From Computer Science","author":"L. Moss","year":"1991","unstructured":"Moss, L., 1991, ?Completeness theorems for logics of feature structures?, Indiana University Logic Group Preprint No. IULG-91-2. To appear inProceedings of the MSRI Workshop on Logic From Computer Science, Y. Moschovakis, ed., Berlin: Springer Verlag."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0020-0190(85)90127-9","volume":"20","author":"S. Passy","year":"1985","unstructured":"Passy, S. and Tinchev, T., 1985, ?PDL with data constants?,Information Processing Letters 20, 35?41.","journal-title":"Information Processing Letters"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0890-5401(91)90026-X","volume":"93","author":"S. Passy","year":"1991","unstructured":"Passy, S. and Tinchev, T., 1991, ?An essay in combinatory dynamic logic?,Information and Computation 93, 263?332.","journal-title":"Information and Computation"},{"key":"CR35","first-page":"123","volume-title":"Proceedings of the 10th International Conference on Computational Linguistics and the 22nd Annual Meeting of the Association for Computational Linguistics","author":"F Pereira","year":"1984","unstructured":"Pereira, F and Shieber, S., 1984, ?The semantics of grammar formalisms seen as computer languages?, pp. 123?129 inProceedings of the 10th International Conference on Computational Linguistics and the 22nd Annual Meeting of the Association for Computational Linguistics, Stanford, California."},{"key":"CR36","unstructured":"Pollard, C. and Sag, I.,Information-Based Syntax and Semantics: Volume 1 ? Fundamentals, CSLI Lecture Notes13, Stanford."},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"Pratt, V., 1979, ?Models of program logics?, pp. 115?122 inProceedings of the 20th IEEE Symposium on Foundations of Computer Science.","DOI":"10.1109\/SFCS.1979.24"},{"key":"CR38","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198243113.001.0001","volume-title":"Past, Present and Future","author":"A. Prior","year":"1967","unstructured":"Prior, A., 1967,Past, Present and Future, Oxford: Oxford University Press."},{"key":"CR39","volume-title":"DYANA deliverable R3.2.A","author":"M. Reape","year":"1991","unstructured":"Reape, M., 1991,An Introduction to the Semantics of Unification-Based Grammar Formalisms, DYANA deliverable R3.2.A, Edinburgh: Centre for Cognitive Science."},{"key":"CR40","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"R. Robinson","year":"1971","unstructured":"Robinson, R., 1971, ?Undecidability and nonperiodicity for tilings of the plane?,Inventiones Math. 12, 177?209.","journal-title":"Inventiones Math."},{"key":"CR41","series-title":"Studies in Logic, Language and Information","volume-title":"Diamonds and Defaults","author":"D. Roorda","year":"1991","unstructured":"Roorda, D., 1991, ?Dyadic modalities and Lambek calculus?, to appear inDiamonds and Defaults, M. de Rijke, ed., Studies in Logic, Language and Information, Dordrecht: Kluwer."},{"key":"CR42","unstructured":"Rounds, W. and Kasper, R., 1986, ?A complete logical calculus for record structures representing linguistic information?, inProceedings of the 15th Annual Symposium on Logic in Computer Science, Cambridge MA."},{"key":"CR43","unstructured":"Schild, K., 1990, ?A correspondence theory for terminological logics: preliminary report?, inProceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, Australia."},{"key":"CR44","unstructured":"Shieber, S., 1986,An Introduction to Unification-Based Approaches to Grammar, CSLI Lecture Notes4, Stanford."},{"key":"CR45","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/3828.3837","volume":"32","author":"A. Sistla","year":"1985","unstructured":"Sistla, A. and Clarke E, 1985, ?The complexity of propositional linear temporal logics?,J. Assoc. Comput. Mach. 32, 733?749.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR46","volume-title":"IWBS Report 93","author":"G. Smolka","year":"1989","unstructured":"Smolka, G., 1989, ?Feature constraint logics for unification grammars?, IWBS Report 93, Stuttgart: IBM Deutschland."},{"key":"CR47","volume-title":"Handbook of Philosophical Logic 2","author":"J. Benthem van","year":"1984","unstructured":"van Benthem, J., 1984, ?Correspondence theory?, inHandbook of Philosophical Logic 2, D. Gabbay and F. Guenthner, eds., Dordrecht: Reidel."}],"container-title":["Journal of Logic, Language and Information"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01050635.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01050635\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01050635","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T13:00:43Z","timestamp":1586091643000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01050635"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993]]}},"alternative-id":["BF01050635"],"URL":"https:\/\/doi.org\/10.1007\/bf01050635","relation":{},"ISSN":["0925-8531","1572-9583"],"issn-type":[{"value":"0925-8531","type":"print"},{"value":"1572-9583","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}