Theoretical Aspects of Computing – ICTAC 2018: 15th International Colloquium, Stellenbosch, South Africa, October 16–19, 2018, Proceedings (Lecture Notes in Computer Science, 11187)

This book constitutes the refereed proceedings of the 15th International Colloquium on Theoretical Aspects of Computing, ICTAC 2018, held in Stellenbosch, South Africa, in October 2018. The 25 revised full papers presented together with two short and two long invited talks were carefully reviewed and selected from 59 submissions. The ICTAC conference aims at bringing together researchers and practitioners from academia, industry and government to present research and exchange ideas and experience addressing challenges in both theoretical aspects of computing and the exploitation of theory through methods and tools for system development. ICTAC also specifically aims to promote research cooperation between developing and industrial countries. Front Matter ....Pages I-XVII Front Matter ....Pages 1-1 Formal Verification of a Geometry Algorithm: A Quest for Abstract Views and Symmetry in Coq Proofs (Yves Bertot)....Pages 3-10 LTL Semantic Tableaux and Alternating \(\omega \)-automata via Linear Factors (Martin Sulzmann, Peter Thiemann)....Pages 11-34 Front Matter ....Pages 35-35 Proof Nets and the Linear Substitution Calculus (Beniamino Accattoli)....Pages 37-61 Modular Design of Domain-Specific Languages Using Splittings of Catamorphisms (Éric Badouel, Rodrigue Aimé Djeumen Djatcha)....Pages 62-79 An Automata-Based View on Configurability and Uncertainty (Martin Berglund, Ina Schaefer)....Pages 80-98 Formalising Boost POSIX Regular Expression Matching (Martin Berglund, Willem Bester, Brink van der Merwe)....Pages 99-115 Monoidal Multiplexing (Apiwat Chantawibul, Paweł Sobociński)....Pages 116-131 Input/Output Stochastic Automata with Urgency: Confluence and Weak Determinism (Pedro R. D’Argenio, Raúl E. Monti)....Pages 132-152 Layer by Layer – Combining Monads (Fredrik Dahlqvist, Louis Parlant, Alexandra Silva)....Pages 153-172 Layer Systems for Confluence—Formalized (Bertram Felgenhauer, Franziska Rapp)....Pages 173-190 A Metalanguage for Guarded Iteration (Sergey Goncharov, Christoph Rauch, Lutz Schröder)....Pages 191-210 Generating Armstrong ABoxes for \(\mathcal {ALC}\) TBoxes (Henriette Harmse, Katarina Britz, Aurona Gerber)....Pages 211-230 Spatio-Temporal Domains: An Overview (David Janin)....Pages 231-251 Checking Modal Contracts for Virtually Timed Ambients (Einar Broch Johnsen, Martin Steffen, Johanna Beate Stumpf, Lars Tveito)....Pages 252-272 Abstraction of Bit-Vector Operations for BDD-Based SMT Solvers (Martin Jonáš, Jan Strejček)....Pages 273-291 Weak Bisimulation Metrics in Models with Nondeterminism and Continuous State Spaces (Ruggero Lanotte, Simone Tini)....Pages 292-312 Symbolic Computation via Program Transformation (Henrich Lauko, Petr Ročkai, Jiří Barnat)....Pages 313-332 Double Applicative Functors (Härmel Nestra)....Pages 333-353 Checking Sequence Generation for Symbolic Input/Output FSMs by Constraint Solving (Omer Nguena Timo, Alexandre Petrenko, S. Ramesh)....Pages 354-375 Explicit Auditing (Wilmer Ricciotti, James Cheney)....Pages 376-395 Complexity and Expressivity of Branching- and Alternating-Time Temporal Logics with Finitely Many Variables (Mikhail Rybakov, Dmitry Shkatov)....Pages 396-414 Complexity Results on Register Context-Free Grammars and Register Tree Automata (Ryoma Senda, Yoshiaki Takata, Hiroyuki Seki)....Pages 415-434 Information Flow Certificates (Manuel Töws, Heike Wehrheim)....Pages 435-454 The Smallest FSSP Partial Solutions for One-Dimensional Ring Cellular Automata: Symmetric and Asymmetric Synchronizers (Hiroshi Umeo, Naoki Kamikawa, Gen Fujita)....Pages 455-471 Convex Language Semantics for Nondeterministic Probabilistic Automata (Gerco van Heerdt, Justin Hsu, Joël Ouaknine, Alexandra Silva)....Pages 472-492 Fast Computations on Ordered Nominal Sets (David Venhoek, Joshua Moerman, Jurriaan Rot)....Pages 493-512 Non-preemptive Semantics for Data-Race-Free Programs (Siyang Xiao, Hanru Jiang, Hongjin Liang, Xinyu Feng)....Pages 513-531 Back Matter ....Pages 533-533