{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:06Z","timestamp":1760202726190},"reference-count":80,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p> Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the frameworks of finite automata for strings and finite tree automata for trees. A possible starting point for such a framework is the formalism of directed acyclic graph (DAG) automata, defined by Kamimura and Slutzki and extended by Quernheim and Knight. In this article, we study the latter in depth, demonstrating several new results, including a practical recognition algorithm that can be used for inference and learning with models defined on DAG automata. We also propose an extension to graphs with unbounded node degree and show that our results carry over to the extended formalism. <\/jats:p>","DOI":"10.1162\/coli_a_00309","type":"journal-article","created":{"date-parts":[[2017,12,14]],"date-time":"2017-12-14T20:23:10Z","timestamp":1513282990000},"page":"119-186","source":"Crossref","is-referenced-by-count":9,"title":["Weighted DAG Automata for Semantic Graphs"],"prefix":"10.1162","volume":"44","author":[{"given":"David","family":"Chiang","sequence":"first","affiliation":[{"name":"University of Notre Dame"}]},{"given":"Frank","family":"Drewes","sequence":"additional","affiliation":[{"name":"University of Ume\u00e5"}]},{"given":"Daniel","family":"Gildea","sequence":"additional","affiliation":[{"name":"University of Rochester"}]},{"given":"Adam","family":"Lopez","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"University of Padua"}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90070-3"},{"key":"bib2","unstructured":"Abend, Omri and Ari Rappoport. 2013. Universal conceptual cognitive annotation (UCCA). In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 228\u2013238, Sofia."},{"key":"bib3","doi-asserted-by":"crossref","unstructured":"Abney, Steven, David McAllester, and Fernando Pereira. 1999. Relating probabilistic grammars and automata. In Proceedings of the 37th Annual Conference of the Association for Computational Linguistics (ACL-99), pages 542\u2013549, College Park, MD.","DOI":"10.3115\/1034678.1034759"},{"key":"bib5","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_10"},{"key":"bib6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.02.004"},{"key":"bib7","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"bib8","unstructured":"Banarescu, Laura, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract meaning representation for sembanking. In Proceedings of the Linguistic Annotation Workshop, pages 178\u2013186, Sofia."},{"key":"bib9","unstructured":"Bar-Hillel, Yehoshua, Micha Perles, and Eli Shamir. 1961. On formal properties of simple phrase structure grammars. Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14(2):143\u2013172."},{"key":"bib10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692060"},{"key":"bib11","unstructured":"Baum, Leonard E. 1972. An inequality and associated maximization technique in statistical estimation for probabilistic functions of Markov processes. In Inequalities III: Proceedings of the Third Symposium on Inequalities, pages 1\u20138, Los Angeles, CA."},{"key":"bib12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_40"},{"key":"bib14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30000-9_33"},{"key":"bib16","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017142"},{"key":"bib17","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1043"},{"key":"bib19","doi-asserted-by":"publisher","DOI":"10.3115\/981344.981378"},{"key":"bib21","unstructured":"Charniak, Eugene. 1997. Statistical parsing with a context-free grammar and word statistics. In Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, pages 598\u2013603, Providence, RI."},{"key":"bib22","unstructured":"Chi, Zhiyi. 1999. Statistical properties of probabilistic context-free grammars. Computational Linguistics, 25:131\u2013160."},{"key":"bib23","unstructured":"Chiang, David. 2012. Hope and fear for discriminative training of statistical translation models. Journal of Machine Learning Research, 13(1):1159\u20131187."},{"key":"bib24","unstructured":"Chiang, David, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, Bevan Jones, and Kevin Knight. 2013. Parsing graphs with hyperedge replacement grammars. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (ACL-13), pages 924\u2013932, Sofia."},{"key":"bib25","doi-asserted-by":"publisher","DOI":"10.3115\/976909.979620"},{"key":"bib26","unstructured":"Collins, Michael and James Brooks. 1995. Prepositional phrase attachment through a backed-off model. In Proceedings of the Third Workshop on Very Large Corpora, pages 27\u201338, Cambridge, MA."},{"key":"bib27","unstructured":"Comon, Hubert, Max Dauchet, R\u00e9mi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison, and Marc Tommasi. 2002. Tree Automata Techniques and Applications. Internet publication available at http:\/\/www.grappa.univ-lille3.fr\/tata."},{"key":"bib28","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"bib31","unstructured":"Drewes, Frank and J\u00e9r\u00f4me Leroux. 2015. Structurally cyclic Petri nets. Logical Methods in Computer Science, 11:1\u20139."},{"key":"bib32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48057-1_15"},{"key":"bib33","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2799"},{"key":"bib34","doi-asserted-by":"crossref","unstructured":"Eisner, Jason. 2002. Parameter estimation for probabilistic finite-state transducers. In Proceedings of the 40th Annual Conference of the Association for Computational Linguistics (ACL-02), pages 1\u20138, Philadelphia, PA.","DOI":"10.3115\/1073083.1073085"},{"key":"bib35","unstructured":"Esparza, Javier and Mogens Nielsen. 1994. Decidability issues for Petri nets\u2014a survey. Elektronische Informationsverarbeitung und Kybernetik, 30:143\u2013160."},{"key":"bib36","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060674"},{"key":"bib37","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/N16-1087"},{"key":"bib38","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1134"},{"key":"bib39","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1986.10478342"},{"key":"bib40","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2003.1210058"},{"key":"bib41","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.006"},{"key":"bib43","doi-asserted-by":"crossref","unstructured":"Gildea, Daniel and Daniel Jurafsky. 2000. Automatic labeling of semantic roles. In Proceedings of the 38th Annual Conference of the Association for Computational Linguistics (ACL-00), pages 512\u2013520, Hong Kong.","DOI":"10.3115\/1075218.1075283"},{"key":"bib44","unstructured":"Gogate, Vibhav and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Uncertainty in Artificial Intelligence (UAI), pages 201\u2013208, Banff."},{"key":"bib45","unstructured":"Goodman, Joshua. 1999. Semiring parsing. Computational Linguistics, 25(4):573\u2013605."},{"key":"bib47","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-18771-5_41"},{"key":"bib49","doi-asserted-by":"publisher","DOI":"10.3115\/1614049.1614064"},{"key":"bib50","unstructured":"Jensen, Finn V., Steffen L. Lauritzen, and Kristian G. Olesen. 1990. Bayesian updating in causal probabilistic networks by local computations. Computational Statistics Quarterly, 4:269\u2013282."},{"key":"bib51","doi-asserted-by":"crossref","unstructured":"Johnson, Mark, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic \u201cunification-based\u201d grammars. In Proceedings of the 37th Annual Conference of the Association for Computational Linguistics (ACL-99), pages 535\u2013541, College Park, MD.","DOI":"10.3115\/1034678.1034758"},{"key":"bib52","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90438-1"},{"key":"bib53","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90012-8"},{"key":"bib56","unstructured":"Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Machine Learning: Proceedings of the Eighteenth International Conference (ICML 2001), pages 282\u2013289, Stanford, CA."},{"key":"bib57","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359853"},{"key":"bib58","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90051-5"},{"key":"bib59","doi-asserted-by":"publisher","DOI":"10.1016\/0885-2308(90)90022-X"},{"key":"bib60","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289017"},{"key":"bib61","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W15-4502"},{"key":"bib62","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1114"},{"key":"bib63","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.07.024"},{"key":"bib64","doi-asserted-by":"publisher","DOI":"10.1137\/070699160"},{"key":"bib65","unstructured":"Marcus, Mitchell P., Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313\u2013330."},{"key":"bib66","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S16-1166"},{"key":"bib67","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"bib68","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70939-8_28"},{"key":"bib69","unstructured":"Ochma\u0144ski, Edward. 1985. Regular behaviour of concurrent systems. Bulletin of the European Association for Theoretical Computer Science, 27:56\u201367."},{"key":"bib70","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S15-2153"},{"key":"bib71","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2008"},{"key":"bib72","unstructured":"Oepen, Stephan and Jan Tore L\u00f8nning. 2006. Discriminant-based MRS banking. In International Conference on Language Resources and Evaluation (LREC), pages 1250\u20131255, Genoa."},{"key":"bib73","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1119"},{"key":"bib74","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/K15-1004"},{"key":"bib75","doi-asserted-by":"crossref","unstructured":"Petrov, Slav, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 433\u2013440, Sydney.","DOI":"10.3115\/1220175.1220230"},{"key":"bib77","doi-asserted-by":"publisher","DOI":"10.36045\/bbms\/1103408550"},{"key":"bib78","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73208-2_33"},{"key":"bib79","unstructured":"Quattoni, Ariadna, Michael Collins, and Trevor Darrell. 2004. Conditional random fields for object recognition. In Advances in Neural Information Processing Systems (NIPS-17), pages 1097\u20131104, Vancouver."},{"key":"bib80","unstructured":"Quernheim, Daniel and Kevin Knight. 2012. Towards probabilistic acceptors and transducers for feature structures. In Proceedings of the Sixth Workshop on Syntax, Semantics and Structure in Statistical Translation (SSST), pages 76\u201385, Jeju Island."},{"key":"bib81","unstructured":"Ramshaw, Lance and Mitch Marcus. 1995. Text chunking using transformation-based learning. In Proceedings of the Third Workshop on Very Large Corpora, pages 82\u201394, Cambridge, MA."},{"key":"bib82","unstructured":"Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 133\u2013142, Philadelphia, PA."},{"key":"bib84","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"bib85","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.03.004"},{"key":"bib86","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531015"},{"key":"bib88","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.4.477"},{"key":"bib89","unstructured":"Snijders, Tom A. B. 2002. Markov chain Monte Carlo estimation of exponential random graph models. Journal of Social Structure, 3(2):1\u201340."},{"key":"bib90","doi-asserted-by":"publisher","DOI":"10.1162\/089120101753342653"},{"key":"bib91","doi-asserted-by":"crossref","unstructured":"Thomas, Wolfgang. 1991. On logics, tilings, and automata. In Proceedings of the 18th International Colloquium on Automata, Languages and Programming, pages 441\u2013454, Madrid.","DOI":"10.1007\/3-540-54233-7_154"},{"key":"bib92","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/029\/02"},{"key":"bib93","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of the 25th Annual Conference of the Association for Computational Linguistics (ACL-87), pages 104\u2013111, Stanford, CA.","DOI":"10.3115\/981175.981190"},{"key":"bib94","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P15-2141"},{"key":"bib95","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1040"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:28:11Z","timestamp":1615584491000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/44\/1\/119-186\/1591"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":80,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1162\/COLI_a_00309"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00309","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3]]}}}