Skip to main content
SpringerLink
Log in
Book cover

Jewels are Forever

Contributions on Theoretical Computer Science in Honor of Arto Salomaa

  • Book
  • © 1999

Overview

Editors:
  1. Juhani Karhumäki

    1. Department of Mathematics and Turku Centre for Computer Science, University of Turku, Turku, Finland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Hermann Maurer

    1. Institutes for Information Processing and Computer Supported Media (IICM), Technical University of Graz, Graz, Austria

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Gheorghe Păun

    1. Institute of Mathematics, Romanian Academy of Sciences, Bucharest, Romania

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Grzegorz Rozenberg

    1. Department of Computer Science, Leiden University, Leiden, The Netherlands

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • A comprehensive state of the art in theoretical computer science

  • Original articles by leading experts in automata theory, formal languages and combinatorics of words

  • Includes supplementary material: sn.pub/extras

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

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.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 (32 chapters)

  1. Front Matter

    Pages I-XXX
    Download chapter PDF

  2. Automata I: Finite State Machines

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Semilattices of Fault Semiautomata

      • Janusz A. Brzozowski, Helmut Jürgensen
      Pages 3-15

    3. Thompson Languages

      • Dora Giammarresi, Jean-Luc Ponty, Derick Wood
      Pages 16-24

    4. On Some Special Classes of Regular Languages

      • Balázs Imreh, Masami Ito
      Pages 25-34

    5. Synchronized Shuffle and Regular Languages

      • Michel Latteux, Yves Roos
      Pages 35-44

    6. Synchronization Expressions: Characterization Results and Implementation

      • Kai Salomaa, Sheng Yu
      Pages 45-56

  3. Automata II: More General Devices

    1. Front Matter

      Pages 57-57
      Download chapter PDF

    2. Uniformization of Rational Relations

      • Christian Choffrut, Serge Grigorieff
      Pages 59-71

    3. Tree-Walking Pebble Automata

      • Joost Engelfriet, Hendrik Jan Hoogeboom
      Pages 72-83

    4. Counter Machines: Decision Problems and Applications

      • Oscar H. Ibarra, Jianwen Su
      Pages 84-96

    5. On the Equivalence of Finite Substitutions and Transducers

      • Juhani Karhumäki, Leonid P. Lisovik
      Pages 97-108

    6. Complementation of Büchi Automata Revisited

      • Wolfgang Thomas
      Pages 109-120

  4. Automata with Multiplicities

    1. Front Matter

      Pages 121-121
      Download chapter PDF

    2. Languages Accepted by Integer Weighted Finite Automata

      • Vesa Halava, Tero Harju
      Pages 123-134

    3. A Power Series Approach to Bounded Languages

      • Juha Honkala
      Pages 135-144

    4. Full Abstract Families of Tree Series I

      • Werner Kuich
      Pages 145-156

    5. Linear Automata, Rational Series and a Theorem of Fine and Wilf

      • Giovanna Melideo, Cesidia Pasquarelli, Stefano Varricchio
      Pages 157-168

  5. Formal Languages

    1. Front Matter

      Pages 169-169
      Download chapter PDF

    2. Numerical Parameters of Evolutionary Grammars

      • Jürgen Dassow
      Pages 171-181
Back to top

Keywords

About this book

Dedicated to Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday, this book is a tribute to him on behalf of the theoretical computer science community. The contributions are written by internationally recognized scientists and cover most of Salomaa's many research areas. Due to its representative selection of classic and cutting edge trends in theoretical computer science, the book constitutes a comprehensive state-of-the-art survey.
The contributions are in such central areas as automata theory, algorithms and complexity, and combinatorics of words. But not only that, they take up new areas such as regular sets and biocomputing. While some are survey articles of fundamental topics, most are original research papers.

Editors and Affiliations

  • Department of Mathematics and Turku Centre for Computer Science, University of Turku, Turku, Finland

    Juhani Karhumäki

  • Institutes for Information Processing and Computer Supported Media (IICM), Technical University of Graz, Graz, Austria

    Hermann Maurer

  • Institute of Mathematics, Romanian Academy of Sciences, Bucharest, Romania

    Gheorghe Păun

  • Department of Computer Science, Leiden University, Leiden, The Netherlands

    Grzegorz Rozenberg

Bibliographic Information

  • Book Title: Jewels are Forever

  • Book Subtitle: Contributions on Theoretical Computer Science in Honor of Arto Salomaa

  • Editors: Juhani Karhumäki, Hermann Maurer, Gheorghe Păun, Grzegorz Rozenberg

  • DOI: https://doi.org/10.1007/978-3-642-60207-8

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1999

  • Softcover ISBN: 978-3-642-64304-0Published: 16 September 2011

  • eBook ISBN: 978-3-642-60207-8Published: 06 December 2012

  • Edition Number: 1

  • Number of Pages: XXX, 379

  • Topics: Algorithm Analysis and Problem Complexity, Combinatorics, Computer Appl. in Life Sciences

Publish with us

Policies and ethics

Back to top

Search

Navigation