NDLI: The nonexistence of finite axiomatisations for CCS congruences

Please wait, while we are loading the content...

2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science

2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

2012 27th Annual IEEE Symposium on Logic in Computer Science

2011 IEEE 26th Annual Symposium on Logic in Computer Science

2010 25th Annual IEEE Symposium on Logic in Computer Science

2009 24th Annual IEEE Symposium on Logic In Computer Science

2008 23rd Annual IEEE Symposium on Logic in Computer Science

22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007)

21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)

20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05)

Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004.

18th Annual IEEE Symposium of Logic in Computer Science, 2003. Proceedings.

Proceedings 17th Annual IEEE Symposium on Logic in Computer Science

Proceedings 16th Annual IEEE Symposium on Logic in Computer Science

Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.99CB36332)

Proceedings. 14th Symposium on Logic in Computer Science (Cat. No. PR00158)

Proceedings. Thirteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No.98CB36226)

Proceedings of Twelfth Annual IEEE Symposium on Logic in Computer Science

Proceedings 11th Annual IEEE Symposium on Logic in Computer Science

Proceedings of Tenth Annual IEEE Symposium on Logic in Computer Science

Proceedings Ninth Annual IEEE Symposium on Logic in Computer Science

[1993] Proceedings Eighth Annual IEEE Symposium on Logic in Computer Science

[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science

[1991] Proceedings Sixth Annual IEEE Symposium on Logic in Computer Science

[1990] Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science

Type reconstruction in finite-rank fragments of the polymorphic lambda -calculus

Polymorphism, set theory, and call-by-value

Universal domains in the theory of denotational semantics of programming languages

The classification of continuous domains

A decision procedure for a class of set constraints

A constraint sequent calculus

Solving inequations in terms algebras

The dynamic logic of permission

A theory of nonmonotonic rule systems

The semantics of reflected proof

Equation solving using modal transition systems

Three logics for branching bisimulation

Reactive, generative, and stratified models of probabilistic processes

The nonexistence of finite axiomatisations for CCS congruences

0-1 laws for infinitary logics

Implicit definability on finite structures and unambiguous computations

ALOGTIME and a conjecture of S.A. Cook

On the expression of monadic second-order graph properties without quantifications over sets of edges

Normal process representatives

A categorical linear framework for Petri nets

A linear semantics for allowed logic programs

Programming in equational logic: beyond strong sequentiality

The theory of ground rewrite systems is decidable

Well rewrite orderings

A constructive proof of Higman's lemma

Syntactic theories and unification

Proof transformations for equational theories

A new AC unification algorithm with an algorithm for solving systems of diophantine equations

On subsumption and semiunification in feature algebras

Completeness for typed lazy inequalities

Conditional lambda-theories and the verification of static properties of programs

Single-threaded polymorphic lambda calculus

Extensional PERs

A PER model of polymorphism and recursive types

Effective domains and intrinsic structure

A logic of concrete time intervals

Real-time logics: complexity and expressiveness

Explicit clock temporal logic

Model-checking for real-time systems

Symbolic model checking: 10/sup 20/ states and beyond

When is 'partial' adequate? A logic-based proof technique using partial specifications

Modelling shared state in a shared action model

On the power of bounded concurrency. III. Reasoning about programs

New foundations for fixpoint computations

Recursive types reduced to inductive types

Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science (90CH2897-7)

On the limits of efficient temporal decidability

[1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science

[1988] Proceedings. Third Annual Information Symposium on Logic in Computer Science

The nonexistence of finite axiomatisations for CCS congruences

Content Provider	IEEE Xplore Digital Library
Author	Moller, F.
Copyright Year	1990
Description	Author affiliation: Dept. of Comput. Sci., Edinburgh Univ., UK (Moller, F.)
Abstract	Equatorial axiomatizations for congruences over a simple sublanguage of R. Milner's (1980) process algebra CCS (calculus of communicating systems) are examined. It is shown that no finite set of equational axioms can completely characterize any reasonably defined congruence which is at least as strong as Milner's strong congruence. In the case of strong congruence, this means that the expansion theorem of CCS cannot be replaced by any finite collection of equational axioms. Moreover, the author isolates a source of difficulty in axiomatizing any reasonable noninterleaving semantic congruence, where the expansion theorem fails to hold.
Starting Page	142
Ending Page	153
File Size	815225
Page Count	12
File Format	PDF
ISBN	0818620730
DOI	10.1109/LICS.1990.113741
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1990-06-04
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Carbon capture and storage Equations Calculus Concurrent computing Computer science Algebra Interleaved codes Writing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in