Nested semantics over finite trees are equationally hard

DOI10.1016/J.IC.2004.02.001zbMATH Open1101.68690OpenAlexW2158342623MaRDI QIDQ598202FDOQ598202

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/

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

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)

Cites Work

• Structured operational semantics and bisimulation as a congruence
• The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
• Process algebra for synchronous communication
• Algebraic laws for nondeterminism and concurrency
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• CCS expressions, finite state processes, and three problems of equivalence
• Formal verification of parallel programs
• The equational theory of pomsets
• Title not available (Why is that?)
• Undecidable equivalences for basic process algebra
• Bisimulation equivalence is decidable for all context-free processes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonaxiomatisability of equivalences over finite state processes
• The max-plus algebra of the natural numbers has no finite equational basis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decidability of bisimulation equivalence for process generating context-free languages
• A menagerie of non-finitely based process semantics over BPA* – from ready simulation to completed traces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (15)

• Coinductive Characterisations Reveal Nice Relations Between Preorders and Equivalences
• Title not available (Why is that?)
• On Finite Bases for Weak Semantics: Failures Versus Impossible Futures
• Ready to preorder: an algebraic and general proof
• Title not available (Why is that?)
• 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
• Nested semantics over finite trees are equationally hard (invited talk)
• A linear-time-branching-time spectrum for behavioral specification theories
• On finite alphabets and infinite bases
• A Linear-Time–Branching-Time Spectrum of Behavioral Specification Theories
• Title not available (Why is that?)

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)