Impossibility results for the equational theory of timed CCS

L. Aceto, A. Ingólfsdóttir, M. Mousavi

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)
    83 Downloads (Pure)

    Abstract

    We study the equational theory of Timed CCS as proposed by Wang Yi in CONCUR’90. Common to Wang Yi’s paper, we particularly focus on a class of linearly-ordered time domains exemplified by the positive real or rational numbers. We show that, even when the set of basic actions is a singleton, there are parallel Timed CCS processes that do not have any sequential equivalent and thus improve on the Gap Theorem for Timed CCS presented by Godskesen and Larsen in FSTTCS’92. Furthermore, we show that timed bisimilarity is not finitely based both for single-sorted and two-sorted presentations of Timed CCS. We further strengthen this result by showing that, unlike in some other process algebras, adding the untimed or the timed left-merge operator to the syntax and semantics of Timed CCS does not solve the axiomatizability problem.
    Original languageEnglish
    Title of host publicationProceedings 2nd Conference on Algebra and Coalgebra in Computer Science (CALCO 2007) 20-24 August 2007, Bergen, Norway
    EditorsT. Mossakowski, U. Montanari, M. Haveraaen
    Place of PublicationBerlin
    PublisherSpringer
    Pages80-95
    ISBN (Print)978-3-540-73857-2
    DOIs
    Publication statusPublished - 2007
    Eventconference; CALCO 2007, Bergen, Norway; 2007-08-20; 2007-08-24 -
    Duration: 20 Aug 200724 Aug 2007

    Publication series

    NameLecture Notes in Computer Science
    Volume4624
    ISSN (Print)0302-9743

    Conference

    Conferenceconference; CALCO 2007, Bergen, Norway; 2007-08-20; 2007-08-24
    Period20/08/0724/08/07
    OtherCALCO 2007, Bergen, Norway

    Fingerprint

    Dive into the research topics of 'Impossibility results for the equational theory of timed CCS'. Together they form a unique fingerprint.

    Cite this