Search

This volume contains the proceedings of the 18th International workshop AUTOMATA and the 3rd international symposium JAC. AUTOMATA workshop series aims at gathering researchers from all over the world working in fundamental aspects of cellular automata and related discrete complex systems. Topics cover (although they are not limited to): dynamics, topological, ergodic and algebraic aspects, algorithmic and complexity issues, emergent properties, formal language processing, symbolic dynamics, models of parallelism and distributed systems, phenomenological descriptions, scientific modeling and practical applications. JAC (Journ\'ees Automates Cellulaires) is a bi-annual symposium covering the same topics and was created to have a very high standard international conference in the domain. This one will be the third event of the series after Uz\`es (2008, France), Turku (2010, Finland)., Comment: EPTCS 90, 2012

Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes., Comment: In Proceedings AUTOMATA&JAC 2012, arXiv:1208.2498

Computability logic (CoL) (see http://www.cis.upenn.edu/~giorgi/cl.html) is a recently introduced semantical platform and ambitious program for redeveloping logic as a formal theory of computability, as opposed to the formal theory of truth that logic has more traditionally been. Its expressions represent interactive computational tasks seen as games played by a machine against the environment, and "truth" is understood as existence of an algorithmic winning strategy. With logical operators standing for operations on games, the formalism of CoL is open-ended, and has already undergone series of extensions. This article extends the expressive power of CoL in a qualitatively new way, generalizing formulas (to which the earlier languages of CoL were limited) to circuit-style structures termed cirquents. The latter, unlike formulas, are able to account for subgame/subtask sharing between different parts of the overall game/task. Among the many advantages offered by this ability is that it allows us to capture, refine and generalize the well known independence-friendly logic which, after the present leap forward, naturally becomes a conservative fragment of CoL, just as classical logic had been known to be a conservative fragment of the formula-based version of CoL. Technically, this paper is self-contained, and can be read without any prior familiarity with CoL., Comment: LMCS 7 (2:1) 2011