{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T02:48:34Z","timestamp":1778554114185,"version":"3.51.4"},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>The paper formulates the Hays and Gaifman dependency grammar (HGDG) in terms of constraints on a string based encoding of dependency trees and develops an approach to obtain a regular approximation for these grammars. Our encoding of dependency trees uses brackets in a novel fashion: pairs of brackets indicate dependencies between pairs of positions rather than boundaries of phrases. This leads to several advantages: (i) HGDG rules over the balanced bracketing can be expressed using regular languages. (ii) A new homomorphic representation for context-free languages is obtained. (iii) A star-free regular approximation for the original projective dependency grammar is obtained by limiting the number of stacked dependencies. (iv) By relaxing certain constraints, the encoding can be extended to non-projective dependency trees and graphs, (v) strong generative power of HGDGs can now be characterized through sets of bracketed strings.<\/jats:p>","DOI":"10.1142\/s0129054105003169","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"565-579","source":"Crossref","is-referenced-by-count":4,"title":["APPROXIMATING DEPENDENCY GRAMMARS THROUGH INTERSECTION OF STAR-FREE REGULAR LANGUAGES"],"prefix":"10.1142","volume":"16","author":[{"given":"ANSSI","family":"YLI-JYR\u00c4","sequence":"first","affiliation":[{"name":"Department of General Linguistics, University of Helsinki, P.O. Box 9, FIN-00014 University of Helsinki, Finland"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Finite state morphology","author":"Beesley K. R.","year":"2003"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"rf3","volume-title":"An introduction to dependency grammar","author":"Debusmann R.","year":"2000"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90232-9"},{"key":"rf7","volume-title":"Introduction to formal language theory","author":"Harrison M. A.","year":"1978"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.2307\/411934"},{"key":"rf9","volume-title":"Link2tree: A dependency-constituency converter","author":"H\u00f6fler S.","year":"2002"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"rf13","volume-title":"The Danish Dependency Treebank Website","author":"Kromann M. T.","year":"2003"},{"key":"rf17","unstructured":"S.\u00a0Marcus, Algebraic linguistics; analytical models, Mathematics in Science and Engineering\u00a029 (Academic Press, New York and London, 1967)\u00a0pp. 200\u2013246."},{"key":"rf19","volume-title":"Dependency syntax: Theory and practice","author":"Mel'\u010duk I. A.","year":"1988"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1162\/089120103322753338"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.2307\/412278"},{"key":"rf24","doi-asserted-by":"crossref","unstructured":"E.\u00a0Roche, Finite-state language processing (A Bradford Book, MIT Press, Cambridge, Massachusetts, 1997)\u00a0pp. 241\u2013281.","DOI":"10.7551\/mitpress\/3007.001.0001"},{"key":"rf25","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3007.001.0001","volume-title":"Finite-state language processing","author":"Roche E.","year":"1997"},{"key":"rf27","volume-title":"\u00c9l\u00e9ments de syntaxe structurale","author":"Tesni\u00e8re L.","year":"1959"},{"key":"rf28","first-page":"53","volume":"11","author":"Wrathall C.","journal-title":"R. A. I. R. O. Informatique th\u00e9orique\/Theoretical Computer Science"},{"key":"rf32","volume-title":"Proceedings of the Eindhoven FASTAR Days 2004","author":"Yli-Jyr\u00e4 A.","year":"2004"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T04:33:06Z","timestamp":1586320386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":18,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0129054105003169"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003169","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}