Paper Info
Title
A pumping lemma and the structure of derivations in the boundary NLC graph languages
Abstract
A pumping lemma is known in the NLC (node-label-controlled) graph languages [4]. However, the pumping lemma has an unnatural point at the first pumping, that is, zero time pumping is not allowed in the pumping lemma. We consider the boundary NLC (BNLC) languages [10]. Then, we obtain a pumping lemma without the unnatural point, similar to one for the NLC graph languages, using the Church-Rosser property of the BNLC graph grammars. We also construct the pumped graphs and provide a constructive proof for our pumping lemma. As a result, we provide the structure of derivations in the BNLC graph grammars and a role of the Church-Rosser property in the NLC graph grammars.
Year
DOI
Venue
1993
10.1016/0020-0255(93)90114-2
Inf. Sci.
Keywords
Field
DocType
boundary nlc graph language
Discrete mathematics,Combinatorics,Handshaking lemma,Line graph,Graph property,Cubic graph,Pumping lemma for regular languages,Pumping lemma for context-free languages,Petersen graph,Voltage graph,Mathematics
Journal
Volume
Issue
ISSN
75
1-2
0020-0255
Citations 
PageRank 
References 
4
0.61
7
Authors
2
Name
Order
Citations
PageRank
Koichi Yamazaki122221.85
Takeo Yaku26923.24