Inherently Reversible Grammars, Logic Programming and Computability

What it is about

A theoretical paper on reversibility: one grammar used both to parse and to generate. If the grammar is a definite logic program, one program serves both directions, since a complete interpreter enumerates the semantics of a string or the strings of a semantics. Dymetman separates two notions. Uniformity of implementation is the shared program. Intrinsic reversibility is a property of the grammar itself: it is finitely reversible when both parsing and generation can be enumerated finitely, possibly after program transformations such as goal reordering or left-recursion removal. He gives examples and counter-examples, including grammars where the semantic side can grow without bound while the string stays small. Under a "moderation" condition on the linguistic description, finite enumerability of parsing is equivalent to that of generation. The paper also shows that acceptance can be undecidable for some grammars. Lexical grammars, where sister constituents simply concatenate their strings, are given as a class with finite reversibility. No experiments are reported.

Ideas

• I1. One table set for both directions. The reader and the encoder should be two uses of one set of rule tables, which is the paper's central claim. Test it: run the encoder on the reader's output for Bible verses, and count how many verses come back exactly. A mismatch names the rule that is not reversible.
• I2. Keep encoder rules close to concatenation. A chunk rule that maps one meta token to its own chunk is closer to a lexical grammar. Count the rules that do not depend on a neighbour or on the whole clause, since these are the ones that can make generation hard, and report that count with the tables.
• I3. A hard bound on candidates per verse. The paper's worst case is non-termination, which matches Mova's fail-fast rule. Put a counted limit on the encoder's search, log each time it is hit, and treat hits as their own residual class.
• I4. A cheap reversibility test per table. For each rule table, map source to meta to source on a corpus and record the mismatch rate. A table with a high rate is the first candidate for a rewrite.

For Mova

The code is tools/translate/src/profile.rs (encoder), tools/translate/src/meta.rs (reader side) and prag (frames, where the same tables should serve both directions). The ideas touch open problems 3 (trees, not strings) and 2 (merges). The paper's theory is for definite programs; the test in I4 is the part to run.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{dymetman1991inherently,
  title = {{Inherently Reversible Grammars, Logic Programming and Computability}},
  author = {Dymetman, Marc},
  booktitle = {Reversible Grammar in Natural Language Processing},
  year = {1991},
  url = {https://aclanthology.org/W91-0104/}
}

References

19 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974. find
2. N.J. Cutland. Computability. Cambridge University Press, Cambridge, England, 1980. find
3. Marc Dymetman. A Generalized Greibach Normal Form for Definite Clause Grammars and the decidability of the offline-parsability problem, May 1991. Paper presented at the Second Meeting on the Mathematics of Language, Yorktown Heights, NY. (To be published). find
4. Marc Dymetman and Pierre Isabelle. Reversible logic grammars for machine translation. In Proceedings of the Second International Conference on Theoretical and Methodological Issues in Machine Translation of Nat-urai Languages, Pittsburgh, PA, June 1988. Carnegie Mellon University. find
5. Marc Dymetman, Pierre Isabelle, and Francois Perrault. A symmetrical approach to parsing and generation. In Proceedings of the 13th International Conference on Computational Linguistics, volume 3, pages 90-96, Helsinki, August 1990. find
6. Mark Johnson. Attribute-Value Logic and the Theory of Grammar. CSLI lecture note No. 16. Center for the Study of Language and Information, Stanford, CA, 1988. find
7. John Wylie Lloyd. Foundations of Logic Programming. Springer-Verlag, Berlin, second edition, 1987. find
8. Roger C. Lyndon. Notes on Logic. Van Nostrand, New York, NY, 1966. find
9. Fernando C. N. Pereira and David H. D. Warren. Parsing as deduction. In Proceedings of the ~lth Annual Meeting of the Association for Computational Linguistics, pages 137-144, MIT, Cambridge, MA, June 1983. find
10. Francois Perrault. Un nouveau formalisme de grammaire logique r6versible. Master's thesis, McGill University, Montr6al, Canada, 1991. find
11. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM, 21:120-126, February 1978. find
12. Stuart M. Shieber. A uniform architecture for parsing and generation. In Proceedings of the 12th International Conference on Computational Linguistics, pages 614-619, Budapest, August 1988. find
13. Stuart M. Shieber. Parsing and type inference for natural and computer languages. Technical note 460, SRI International, Menlo Park, CA, 1989. (Ph.D. dissertation, Department of Computer Science, Stanford University). find
14. Stuart M. Shieber, Gertjan van Noord, Robert Moore, and Fernando Pereira. A semantic-head-driven generation algorithm for unification-based formalisms. In Proceedings of the ~7th Annual Meeting of the Association for Computational Linguistics, pages 7-17, Vancouver, BC, Canada, June 1989. find
15. Mark Steedman. Dependency and coordination in the grammar of dutch and english. Language, 61(3):523-568, 1985. find
16. Tomek Strzalkowski and Ping Peng. Automated inversion of logic grammars for generation. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics, pages 212-19, Pittsburgh, PA, June 1990. find
17. Gertjan van Noord. Towards convenient bidirectional grammar formalisms. In Proceedings of the 18th International Conference on Computational Linguistics, volume 2, pages 294-298, Helsinki, August 1990. find
18. Gertjan van Noord. BUG: A directed bottom-up generator for unification based formalisms. Technical report, RUU, Department of Linguistics, Utrecht, Holland, 1989. find
19. Remi Zajac. A uniform architecture for parsing, generation and transfer. In Proceedings of the Workshop on Reversible Grammars in Natural Language Processing, Berkeley, CA, 1991. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/dymetman-1991-inherently-reversible-grammars-logic-programming/