Nested semantics over finite trees are equationally hard

DOI10.1016/J.IC.2004.02.001MaRDI QIDQ598202zbMATH OpenOpenAlexFDO

Authors Luca Aceto, Wan Fokkink, Rob van Glabbeek, Anna Ingolfsdottir

Publication date 6 August 2004

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL http://www.brics.dk/NS/03/2/

zbMATH Keywords

ConcurrencyProcess algebraBCCSPComplete axiomatizationsEquational logicHennessy--Milner logicNested simulationNested trace semanticsNon-finitely based algebrasPossible futures

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Nested semantics over finite trees are equationally hard (invited talk)
• scientific article; zbMATH DE number 1688353
• The equational theory of weak complete simulation semantics over BCCSP
• Trace simulation semantics is not finitely based over BCCSP
• Axiomatizing weak simulation semantics over BCCSP

Cites work

• scientific article; zbMATH DE number 1670866 (Why is no real title available?)
• scientific article; zbMATH DE number 1688353 (Why is no real title available?)
• scientific article; zbMATH DE number 4039251 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3770925 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 48157 (Why is no real title available?)
• scientific article; zbMATH DE number 177854 (Why is no real title available?)
• scientific article; zbMATH DE number 1114007 (Why is no real title available?)
• scientific article; zbMATH DE number 2038703 (Why is no real title available?)
• scientific article; zbMATH DE number 1479629 (Why is no real title available?)
• scientific article; zbMATH DE number 1500521 (Why is no real title available?)
• scientific article; zbMATH DE number 795666 (Why is no real title available?)
• scientific article; zbMATH DE number 3316966 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• Algebraic laws for nondeterminism and concurrency
• Bisimulation equivalence is decidable for all context-free processes
• CCS expressions, finite state processes, and three problems of equivalence
• Decidability of bisimulation equivalence for process generating context-free languages
• Formal verification of parallel programs
• Nonaxiomatisability of equivalences over finite state processes
• Process algebra for synchronous communication
• Structured operational semantics and bisimulation as a congruence
• The equational theory of pomsets
• The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
• The max-plus algebra of the natural numbers has no finite equational basis
• Undecidable equivalences for basic process algebra

Cited in

(15)

• Coinductive Characterisations Reveal Nice Relations Between Preorders and Equivalences
• scientific article; zbMATH DE number 7471704 (Why is no real title available?)
• On Finite Bases for Weak Semantics: Failures Versus Impossible Futures
• Ready to preorder: an algebraic and general proof
• scientific article; zbMATH DE number 1688353 (Why is no real title available?)
• Bisimilarity is not finitely based over BPA with interrupt
• Finding compact scheme forests in nested normal form is NP-hard
• Characteristic formulae for relations with nested fixed points
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• Non-finite axiomatisability results via reductions: CSP parallel composition and CCS restriction
• On finite alphabets and infinite bases
• Nested semantics over finite trees are equationally hard (invited talk)
• A linear-time-branching-time spectrum for behavioral specification theories
• A Linear-Time–Branching-Time Spectrum of Behavioral Specification Theories
• scientific article; zbMATH DE number 7559474 (Why is no real title available?)

This page was built for publication: Nested semantics over finite trees are equationally hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q598202)