6th International Conference on Algebraic Informatics (CAI 2015)

September 1–4, 2015 — Stuttgart, Germany

Now open: REGISTRATIONInvited speakersAccepted papersProgramDetailed program (PDF)

Important datesProgram committeeSteering committeeLocal organizing committee

Practical information: How to get there and how to get aroundWhere to stay


CAI is the biennial conference serving the community interested in the intersection of theoretical computer science, algebra, and related areas. In 2015 it will feature invited presentations and a selective single-track program of contributed papers describing original and unpublished research. The proceedings of CAI 2015 will be published in the Lecture Notes in Computer Science (LNCS) series by Springer.


Thank you for your interest in attending CAI 2015. In order to register for the conference, please fill this form and send the filled version to We will confirm your registration details and send you instructions on how to transfer your registration fee. Your registration fee includes admission to all scientific sessions, a copy of the conference proceedings, printed program and various conference materials, refreshments during the coffee breaks, the excursion, and conference dinner.
Registration fee in EUREarlyLate
Full (PhD holders)300350

Early registration deadline: June 26, 2015

To be eligible for the early registration rate, please fill this form and transfer the registration fee before the early registration deadline expires.

Invited speakers

  • Volker Diekert (Universität Stuttgart, Germany): More Than 1700 Years of Word Equations
  • Jarkko Kari (University of Turku, Finland): An Algebraic Geometric Approach to Multidimensional Words
  • Werner Kuich (Vienna University of Technology, Austria): Why We Need Semirings in Automata Theory
  • Mehryar Mohri (New York University, NY, USA): Learning Weighted Automata

Accepted papers

  • Luisa Herrmann and Heiko Vogler. A Chomsky-Schützenberger Theorem for Weighted Automata with Storage
  • Vladimir Zakharov. Equivalence checking problem for finite state transducers over semigroups
  • Manfred Droste, Doreen Heusel and Heiko Vogler. Weighted Unranked Tree Automata over Tree Valuation Monoids and Their Characterization by Weighted Logics
  • Nicolas Borie. Effective Invariant Theory of Permutation Groups using Representation Theory
  • Muhammed F. Esgin, Osmanbey Uzunkol and Mehmet Sabir Kiraz. A New Partial Key Exposure Attack on Multi-Power RSA
  • Deepak Dalai. On the Lower Block Triangular Nature of the Incidence Matrices to Compute the Algebraic Immunity of Boolean Functions
  • Qichao Wang, Norbert Hundeshagen and Friedrich Otto. Weighted Restarting Automata and Pushdown Relations
  • Riccardo Longo, Chiara Marcolla and Massimiliano Sala. Key-Policy Multi-Authority Attribute-Based Encryption
  • Marco Pizzato, Massimiliano Sala and Matteo Piva. Attacking BEAR and LION schemes in a realistic scenario
  • Atsuko Miyaji and Satoru Tanaka. Extended Explicit Relations Between Trace, Definition Field, and Embedding Degree
  • Johannes Osterholzer. Complexity of Uniform Membership of Context-Free Tree Grammars
  • Duc-Phong Le, Nadia El Mbrabet and Chik How Tan. On near prime-order elliptic curves with small embedding degrees
  • Marco Calderini and Massimiliano Sala. On differential uniformity of maps that may hide an algebraic trapdoor
  • Andreas Krebs and Howard Straubing. EF+EX Forest Algebras
  • Marcella Anselmo, Dora Giammarresi and Maria Madonia. Unbordered Pictures: Properties and Construction

Tentative program

Detailed program (PDF download)
Tue, Sep. 1Wed, Sep. 2Thu, Sep. 3Fri, Sep. 4
09:30-10:00 Kuich Kari Diekert
10:30-11:00 break break break
11:00-11:30Herrmann, VoglerZakharovBorie
11:30-12:00Droste, Heusel, VoglerOsterholzer Calderini, Sala
12:00-12:30Wang, Hundeshagen, Otto Anselmo, Giammarresi, MadoniaKrebs, Straubing
12:30-13:00 lunch lunch lunch
14:00-14:30opening Esgin, Uzunkol, Kiraz Excursion
14:30-15:00MohriLongo, Marcolla, Sala
15:00-15:30Pizzato, Sala, Piva
15:30-16:00 break break
16:00-16:30Le, El Mbrabet, Tan business
17:00-17:30Miyaji, Tanaka


Typical contributions to CAI come from the following areas of interest (ordered alphabetically). Papers covering other areas will be given due consideration by the program committee. Papers describing original R&D solutions in those areas are also welcome.

  • abstract machines or systems
  • acceptors and transducers for discrete structures
  • algebraic aspects of cryptography
  • algebraic characterization of logical theories
  • algebraic coding theory
  • algebraic semantics
  • algebraic specifications and algorithms
  • computational number theory
  • decision problems
  • finite and infinite computations
  • formal power series
  • hybrid automata
  • process algebra
  • program construction and refinements
  • term rewriting


We invite all authors to submit their papers (in PDF format) presenting original research work on the topics covered by the conference, electronically via EasyChair to


Submissions should be formatted according to the usual LNCS article style and should not exceed 12 pages (including all references). If additional space is needed, a clearly marked appendix can be added. The appendix will not be published, so the merit and results of the contribution should also be understandable without it.

Simultaneous submission to other conferences with published proceedings is not allowed.

Important dates

  • Submission deadline: April 27, 2015 Monday, May 4, 2015 at 11:59pm PDT (UTC -7h)
  • Notification: May 29, 2015
  • Final version: June 15, 2015
  • Early registration: June 26, 2015
  • Conference: September 1–4, 2015

Program committee

  • Symeon Bozapalidis (Aristotle University of Thessaloniki, Greece)
  • Bruno Courcelle (University of Bordeaux, France)
  • Frank Drewes (Umea University, Sweden)
  • Manfred Droste (Universität Leipzig, Germany)
  • Zoltán Ésik (University of Szeged, Hungary)
  • Tero Harju (University of Turku, Finland)
  • Gregory Kucherov (University Paris-Est, Marne-la-Vallée, France)
  • Andreas Maletti (Universität Stuttgart, Germany)
  • Traian Muntean (Aix-Marseille Université, France)
  • Alexander Okhotin (University of Turku, Finland)
  • Friedrich Otto (Universität Kassel, Germany)
  • Jean Eric Pin (CNRS & Université Paris 7, France)
  • George Rahonis (Aristotle University of Thessaloniki, Greece)
  • Robert Rolland (Aix-Marseille Université, France)
  • Kai Salomaa (Queen's University, Kingston, ON, Canada)
  • Heiko Vogler (Technische Universität Dresden, Germany)
  • Mikhail Volkov (Ural Federal University, Yekaterinburg, Russia)
  • Franz Winkler (J. Kepler Universität, Linz, Austria)

Steering committee

  • Symeon Bozapalidis (Aristotle University of Thessaloniki, Greece)
  • Zoltán Ésik (University of Szeged, Hungary)
  • Werner Kuich (Technische Universität Wien, Vienna, Austria)
  • Arto Salomaa (University of Turku, Finland)

Local organizing committee

  • Fabienne Braune
  • Andreas Maletti
  • Sabrina Mayer
  • Daniel Quernheim
  • Nina Seemann
Contact: cai2015@ims.uni-stuttgart.de

How to get there

  • By airplane: Stuttgart is very conveniently reached via Stuttgart-Echterdingen Airport (STR). Other nearby airports include Frankfurt (FRA), a major hub, and Karlsruhe/Baden-Baden (FKB), served by low-cost carriers. Some airlines offer combined plane/train tickets; if you have a connection via FRA, please consult your airline whether the FRA-STR segment is actually a train (in which case you need to collect your luggage in FRA).
  • By train: Stuttgart is connected by train to all major cities in Germany, as well as many European destinations, such as Paris, Amsterdam, Vienna and Budapest.

How to get around

  • CAI will take place at the University of Stuttgart's Vaihingen campus. The campus is conveniently reached by commuter trains (S-Bahn). All S1, S2 and S3 trains serve the "Universität" station as well as all downtown Stuttgart; in addition, S2 and S3 also serve the airport.
  • From Stuttgart Airport ("Flughafen/Messe"), take the S2 or S3 trains towards Stuttgart Hbf (main station) to get to the conference venue ("Universität") and most hotels (see below).
  • From Stuttgart downtown / main station, take the S1, S2, or S3 trains (towards Herrenberg, Filderstadt, Airport or Vaihingen) to get to the conference venue ("Universität").
  • Fares are determined using a zone system:
    • Airport-CAI: 2 zones (16 minutes)
    • Airport-Downtown: 3 zones (25 minutes)
    • Downtown-CAI: 2 zones (9 minutes)

    Tickets for individual use, multi-trip tickets, and day passes can be purchased from vending machines. Some hotels sell multi-day or week passes.

    Please refer to the public transportation travel planner to plan your trip.

Campus information

CAI will take place at IMS (Pfaffenwaldring 5b). Please refer to this map to find your way on campus (click for larger image). Lunch and refreshments are available from various cafeterias ("Mensa"), as well as the on-campus hotel right next to IMS. There is also a small supermarket on campus.

Where to stay

public transitremarks
< 50 EUR/night
Jugendherberge StuttgartEugensplatz (30 min.)very basic, dormitories and private rooms; transfer or 15 min. walk required
ibis budgetMaybachstr. (30 min.)Transfer required
Hotel LammMineralbäder (30 min.)Transfer required
50–80 EUR/night
Römerhof(almost) on campus, 10 min. walk
Commundoon campusMention that you're attending a conference to get good rates
MercureHauptbahnhof (10 min.)
Hansa/AstoriaFeuersee/Stadtmitte (7-9 min.)these belong together
Motel OneFeuerbach (20 min.) / Hauptbahnhof (10 min.)Feuerbach is cheaper, but requires a transfer
Wyndham AirportAirport (16 min.)Conveniently located at the airport
> 80 EUR/night
PullmanVaihingen (5 min.)
SteigenbergerHauptbahnhof (10 min.)
InterCity HotelHauptbahnhof (10 min.)