Contemporary Mathematics Application of Logic to Combinatorial Sequences and Their Recurrence Relations Eldar Fischer, Tomer Kotek, and Johann A. Makowsky Part 1. Introduction and Synopsis 1. Sequences of integers and their combinatorial interpretations 2. Linear recurrences 3. Logical formalisms 4. Finiteness conditions 5. Logical interpretations of integer sequences Part 2. Guiding Examples 6. The classical recurrence relations 7. Functions, permutations and partitions 8. Trees and forests 9. Graph properties 10. Latin squares Part 3. C-Finite and Holonomic Sequences 11. C-Finite sequences 12. Holonomic sequences Part 4. Modular Recurrence Relations 13. DU-index and Specker index 14. The of logic 15. Structures of bounded degree 16. Structures of unbounded degree References 2010 Mathematics Subject Classification. 03-02, 03C98, 05-02, 05A15, 11B50 . Partially supported by an ISF grant number 1101/06 and an ERC-2007-StG grant number 202405. Partially supported by the Fein Foundation and the Graduate School of the Technion - Israel Institute of Technology. Partially supported by the Israel Science Foundation for the project “Model Theoretic Inter- pretations of Counting Functions” (2007-2010) and the Grant for Promotion of Research by the Technion–Israel Institute of Technology. 2011 American Mathematical Society 1 Volume 558, 2011 cc http://dx.doi.org/10.1090/conm/558/11047
Previous Page Next Page