Paper Info
Title
Iterated TGR languages: membership problem and effective closure properties
Abstract
We show that membership is decidable for languages defined by iterated template-guided recombination systems when the set of templates is regular and the initial language is context-free. Using this result we show that when the set of templates is regular and the initial language is context-free (respectively, regular) we can effectively construct a pushdown automaton (respectively, finite automaton) for the corresponding iterated template-guided recombination language.
Year
DOI
Venue
2006
10.1007/11809678_12
COCOON
Keywords
Field
DocType
pushdown automaton,finite automaton,iterated template-guided recombination system,initial language,iterated tgr language,corresponding iterated template-guided recombination,membership problem,effective closure property
Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Context-free language,Nondeterministic finite automaton,Computer science,Deterministic pushdown automaton,Pushdown automaton,Regular language,Probabilistic automaton,Büchi automaton
Conference
ISBN
Citations 
PageRank 
3-540-36925-2
5
0.59
References 
Authors
5
3
Name
Order
Citations
PageRank
Ian McQuillan19724.72
Kai Salomaa21311138.71
Mark Daley316622.18