The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)

Dana May Latch

Cahiers de Topologie et Géométrie Différentielle Catégoriques (1991)

  • Volume: 32, Issue: 3, page 203-242
  • ISSN: 1245-530X

How to cite

top

Latch, Dana May. "The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)." Cahiers de Topologie et Géométrie Différentielle Catégoriques 32.3 (1991): 203-242. <http://eudml.org/doc/91480>.

@article{Latch1991,
author = {Latch, Dana May},
journal = {Cahiers de Topologie et Géométrie Différentielle Catégoriques},
keywords = {context-free grammar; path algebra; syntactic algebra; fundamental groupoid; homotopy; category small categories; unification algorithm; undecidability},
language = {eng},
number = {3},
pages = {203-242},
publisher = {Dunod éditeur, publié avec le concours du CNRS},
title = {The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)},
url = {http://eudml.org/doc/91480},
volume = {32},
year = {1991},
}

TY - JOUR
AU - Latch, Dana May
TI - The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)
JO - Cahiers de Topologie et Géométrie Différentielle Catégoriques
PY - 1991
PB - Dunod éditeur, publié avec le concours du CNRS
VL - 32
IS - 3
SP - 203
EP - 242
LA - eng
KW - context-free grammar; path algebra; syntactic algebra; fundamental groupoid; homotopy; category small categories; unification algorithm; undecidability
UR - http://eudml.org/doc/91480
ER -

References

top
  1. Baa89 Baader, F., Unification properties of commutative theories: A categorical approach, Proceedings of Category Theory and Computer Science, Manchester, UK, September 1989, LNCS389, Springer Verlag, New York, 1989, 273-299. MR1031568
  2. BaDe87 Backmair, L. & Dershowitz, N., Completion for rewriting modulo a congruence, Proceedings of Rewriting Techniques and Applications, Bordeaux, France, May 1987, LNCS256, Springer Verlag, New York, 1987, 192-203. Zbl0659.68114MR903672
  3. Ba78 Backus, J., Can programming be liberated from the von Neumann style? A functional style and its algebra of programs, Communications of the ACM, 21(1978) 613-641. Zbl0383.68013MR520392
  4. Be75 Benson, D., The basic algebraic structures in categories of derivations, Infor. and Contr., 28(1975) 1-29. Zbl0304.68083MR412248
  5. BiWa88 Bird, R. & Walder, P., Introduction to Functional Programming, Prentice Hall, New York, 1988. 
  6. BHS89 Bürkert, H.-J., Herold, A. & Schnidt-Schauss, M.On equational theories, unification and (un)decidability, J. Symbolic Computation, 8(1989) 3-49. Zbl0684.03004MR1014192
  7. BuRy86 Burstall, R. & Rydeheard, D., The unification of terms: A category-theoretic algorithm, Proceedings of Category Theory and Computer Programming, Guildford, UK, Sept. 1985, LNCS240, Springer Verlag, New York, 1986, 493-505. Zbl0616.68016MR875705
  8. Co65 Cohn, P., Universal Algebra, Harper & Row, New York, 1965. Zbl0141.01002MR175948
  9. DaWe83 Davis, M. & Weuyker, E., Computability, Complexity and Languages, Academic Press, New York, 1983. Zbl0569.68042MR741026
  10. D2Qu78 Denning, P., Dennis, J. & Qualitz, J., Machines, Languages and Computation, Prentice-Hall, Englewood Cliffs, NJ, 1978. Zbl0492.68003
  11. Ei87 Eisenbach, S., Functional Programming: Languages, Tools and Architectures, John Wiley & Sons, New York, 1987. 
  12. Fa84 Fages, F., Associative-commutative unification, Proceedings of the 7th C.A.D.E., LNCS170, Springer Verlag, New York, 1984, 194-208. Zbl0547.03012MR778048
  13. Fr79 Frank, G., Virtual Memory Systems for Closed Applicative Language Interpreters, PhD Dissertation, University of North Carolina at Chapel Hill, 1979. 
  14. FLPS82 Frank, G., Latch, D., Petro, J. & Stanat, D., Applications of algebraic topology of small categories to the semantics of formal functional programming languages, UNC-CH Technical Report in Computer Science #82-009, Chapel Hill, NC, 1982. 
  15. FriLa81 Fritsch, R. & Latch, D., Homotopy inverses for nerve, Math. Z., 177(1981) 147-179. Zbl0456.55014MR612870
  16. GaZi67 Gabriel, P. & Zisman, M., Calculus of Fractions and Homotopy Theory, Springer Verlag, New York, 1967. Zbl0186.56802MR210125
  17. Gi66 Ginsburg, S., Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966. Zbl0184.28401MR211815
  18. Ha78 Harrison, M., Introduction to Formal Language Theory Addison-Wesley, Reading, MA, 1978. Zbl0411.68058MR526397
  19. HaW385 Halpern, J., Williams, J., Wimmers, E., & Winkler, T., Denotational semantics and rewrite rules for FP, Proceedings of the Twelfth ACM Symposium of Principles of Programming Languages, January 1985, 108-120. 
  20. HoU179 Hopcroft, J. & Ullman, J., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading, MA, 1979. Zbl0426.68001MR645539
  21. Hu89 Hudak, P., The conception, evolution and application of functional programming languages, to appear in ACM Computing Surveys. 
  22. Hue75 Huet, G., A unification algorithm for the typed λ-calculus, Theor. Comp. Sci., 1(1975) 25-57. Zbl0332.02035
  23. Hue80 Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. of Assoc. Comp. Mach., 27(1980) 797-821. Zbl0458.68007MR594700
  24. Kn89 Knight, K., Unification: A multidisciplinary survey, ACM Computing Surveys, 21(1989) 93-124. Zbl0677.68098MR1072798
  25. KnBe70 Knuth, D. & Bendix, P., Simple word problems in universal algebras, Computational Problems in Abstract Algebra, Leech J., ed., Pergamon Press, 1970, 263-297. Zbl0188.04902MR255472
  26. LaSc86 Lambek, J. & Scott, P., Introduction to Higher Order Categorical Logic, Cambridge University Press, London, 1986. Zbl0596.03002MR856915
  27. La73 Latch, D., On derived functors of limit, Trans. of Amer. Math. Soc., 181(1973) 155-163. Zbl0272.18007MR323866
  28. La75 Latch, D., The uniqueness of homology for the category of small categories, J. of Pure and Applied Algebra, 9(1975) 221-237. Zbl0363.18008MR460421
  29. La79 Latch, D., A fibred homotopy equivalence and homology theories for the category of small categories, J. of Pure and Applied Algebra, 15(1979) 247-269. Zbl0407.55006MR537499
  30. La89a Latch, D., Finite generation of ambiguity in context free languages, J. of Pure and Applied Algebra, 57(1989) 229-263. Zbl0666.20030MR987314
  31. La89b Latch, D., An application of minimal context-free intersection partitions to rewrite rule consistency checking, Proceedings of the AMS-IMS-SIAM Conference on Categories in Computer Science and Logic, Boulder CO, 1987, AMS Contemporary Mathematics, 92(1989) 241 -260. Zbl0685.68067MR1003202
  32. LaMi74 Latch, D. & Mitchell, B., On the difference between homological and cohomological dimensions, J. of Pure and Applied Algebra, 5(1974) 333-343. Zbl0295.18003MR360755
  33. LaSi88 Latch, D. & Sigal, R., Generating evaluation theorems for functional programming languages, Proceedings of the Third International Symposium on Methodologies for Intelligent Systems, Torino, Italy, October 1988, 47-58. 
  34. LSR90 Latch, D., Sigal, R. & Ruggeri, R., Generating nondeterministic evaluation theorems for functional languages, to appear in Proceedings of the Fourth Workshop on Computer Science Logic, Heidelberg, FRG, October 1990. 
  35. LTW79 Latch, D., Thomason, R. & Wilson, S., Simplicial sets from categories, Math. Z., 164(1979) 195-214. Zbl0408.55019MR516607
  36. LePa81 Lewis, H. & Papadimitriou, K., Elements of the Theory of Computation, Prentice Hall, Englewood Cliffs, NJ., 1981. Zbl0464.68001
  37. Mac71 Mac Lane, S., Categories for the Working Mathematician, Springer Verlag, New York, 1971. Zbl0232.18001MR354798
  38. Mi57 Milnor, J., The geometric realization of a semi-simplicial complex, Ann. Math., 65(1957), 357-362. Zbl0078.36602MR84138
  39. Ne80 Nelson, E., Categorical and topological aspects of formal languages, Math. System Theory13(1980) 255-273. Zbl0471.68053MR572498
  40. Ro65 Robinson, J., A machine-oriented logic based on the resolution principle, J. of Assoc. for Comp. Mach., 12(1965) 23-41. Zbl0139.12303MR170494
  41. Rot88 Rotman, J., An Introduction to Algebraic Topology, Springer Verlag, New York, 1988. Zbl0661.55001MR957919
  42. Ru87 Rust, T., An algebraic model for programming languages, Computer Languages12(1987) 173-195. Zbl0629.68004
  43. RySt87 Rydeheard, D.E. & Stell, J.C., Foundations of equational deduction: A categorical treatment of equational proofs and unification algorithms, Proceedings of Category Theory and Computer Science, Edinburgh, UK, September 1987, LNCS389, Springer Verlag, New York, 1987, 114-139. Zbl0664.03041MR925227
  44. ShSt87 Sterling, E. & Shapiro, R., The Art of PROLOG, MIT Press, Cambridge, MA, 1987. Zbl0605.68002
  45. Si84 Siekmann, J., Universal unification, Proceedings of the 7th C.A.D.E., LNCS170, Springer Verlag, New York, 1984, 1-42. Zbl0547.03011MR778038
  46. Si89 Siekmann, J., Unification theory, J. Symbolic Computation, 7(1989) 207-274. Zbl0678.68098MR993666

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.