Skip to main content
SpringerLink
Log in

Structures in Logic and Computer Science

A Selection of Essays in Honor of A. Ehrenfeucht

  • Book
  • © 1997

Overview

Editors:
  1. Jan Mycielski
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Grzegorz Rozenberg
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Arto Salomaa
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1261)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (22 chapters)

  1. Front Matter

    Download chapter PDF

  2. On the work of Andrzej Ehrenfeucht in model theory

    • Robert Vaught
    Pages 1-13

  3. Syntax vs. semantics on finite structures

    • Natasha Alechina, Yuri Gurevich
    Pages 14-33

  4. Expressive power of unary counters

    • Michael Benedikt, H. Jerome Keisler
    Pages 34-50

  5. Some strange quantifiers

    • Wilfrid Hodges
    Pages 51-65

  6. Pebble games in model theory

    • James F. Lynch
    Pages 66-83

  7. An interpretive isomorphism between binary and ternary relations

    • Dale Myers
    Pages 84-105

  8. Vagueness — A rough set view

    • Zdzislaw Pawlak
    Pages 106-117

  9. Ehrenfeucht games, the composition method, and the monadic theory of ordinal words

    • Wolfgang Thomas
    Pages 118-143

  10. Monadic second order logic and node relations on graphs and trees

    • Roderick Bloem, Joost Engelfriet
    Pages 144-161

  11. Approximating the volume of general Pfaffian bodies

    • Marek Karpinski, Angus Macintyre
    Pages 162-173

  12. Complement-equivalence classes on graphs

    • Ross McConnell
    Pages 174-191

  13. On compact directed acyclic word graphs

    • Maxime Crochemore, Renaud Vérin
    Pages 192-211

  14. Metric entropy and minimax risk in classification

    • David Haussler, Manfred Opper
    Pages 212-235

  15. Of periods, quasiperiods, repetitions and covers

    • Alberto Apostolico, Dany Breslauer
    Pages 236-248

  16. Combinatorics of standard Sturmian words

    • Aldo de Luca
    Pages 249-267

  17. Compactness of systems of equations on completely regular semigroups

    • Tero Harju, Juhani Karhumäki, Mario Petrich
    Pages 268-280

  18. Decision problems concerning algebraic series with noncommuting variables

    • Juha Honkala
    Pages 281-290

  19. Associative shuffle of infinite words

    • Alexandru Mateescu, George Daniel Mateescu
    Pages 291-307

  20. Constructing sequential bijections

    • Christophe Prieur, Christian Choffrut, Michel Latteux
    Pages 308-321
Back to top

Keywords

About this book

This book is dedicated to Andrzej Ehrenfeucht on the occasion of his 65th birthday. On personal invitation by the volume editors, 22 internationally well-known scientists from mathematical logics and theoretical computer science participated in this project honoring an excellent scientist with excellent papers centered around his scientific work.
The 22 invited papers are presented in topical sections on model theory, games and logic, graphs and algorithms, pattern matching and learning, combinatorics of words, algebra of languages, formal language theory, and computational molecular biology.

Bibliographic Information

  • Book Title: Structures in Logic and Computer Science

  • Book Subtitle: A Selection of Essays in Honor of A. Ehrenfeucht

  • Editors: Jan Mycielski, Grzegorz Rozenberg, Arto Salomaa

  • Series Title: Lecture Notes in Computer Science

  • DOI: https://doi.org/10.1007/3-540-63246-8

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1997

  • Softcover ISBN: 978-3-540-63246-7Published: 23 July 1997

  • eBook ISBN: 978-3-540-69242-3Published: 02 July 2005

  • Series ISSN: 0302-9743

  • Series E-ISSN: 1611-3349

  • Edition Number: 1

  • Number of Pages: XII, 376

  • Topics: Theory of Computation, Mathematical Logic and Foundations

Publish with us

Policies and ethics

Back to top

Search

Navigation