Decidability of bisimulation equivalence for process generating context-free languages

Publisher Website
Google Scholar
Abstract
A context-free grammar (CFG) in Greibach Normal Form coincides, in another notation, with a system of guarded recursion equations in Basic Process .$dgebrzd. Hence, to each CFG, aprocess can be assigned absolution, which has as its set of finite traces the context-free language (CFL)determined by that CFG. Although theequality problem for CFLs is unsolvable, the equality problem for the processes determined by CFGS turns out to be solvable. Here, equality on processes is given bya model ofprocess graphs modulobisimulation,equivalence. The proof,is given,by,displaying,a periodic,structure,of the,process,graphs,determmed,by,CFG’S. As a corollary of the periodicity, a short proof of the solvability of the equivalence problem for simple context-free,languages,is given. Categories,and,Subject Descriptors: F. 1.1 [Computation,by Abstract,Devices]: Model,of Computa- tion—A atwnata:,F.3.2 [Logics,and,Meanings,of Programs]:,Semantics,of Programming,Languages —algebraic,approaches,to sema?ztics;,F.4.3 [Mathematical,Logic,and,Formal,Languages]:,Formal Languages—decision,problems General,Terms: Theory Additional Key Words and Phrases: Bisimulation semantics, context-free grammars, context-free languages, process algebra, simple context-free languages The research,of J.A. Bergstra,and,J. W. Klopwas,partially,supported,by ESPRIT project,432:

This publication has 13 references indexed in Scilit: