Paper Info
Title
Decidability of bisimulation equivalence for processes generating context-free languages
Abstract
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:
Year
DOI
Venue
1993
10.1145/174130.174141
Parallel Architectures and Languages Europe
Keywords
DocType
Volume
context-free grammars,bisimulation equivalence,process algebra,process generating context-free language,processes generating context-free languages,bisimulation semantics,context-free language,simple context-free languages,context free language
Journal
40
Issue
ISSN
Citations 
3
0004-5411
141
PageRank 
References 
Authors
15.91
21
3
Search Limit
100141
Name
Order
Citations
PageRank
Jos C. M. Baeten114115.91
Jan A. Bergstra21445140.42
jan willem klop3110396.12