Paper Info
Title
HRNCE grammars - a hypergraph generating system with an eNCE way of rewriting
Abstract
We introduce a hypergraph-generating system, called HRNCE grammars, which is structurally simple and descriptively powerful. An HRNCE grammar replaces a handle (i.e., a hyperedge together with its incident nodes) by a hypergraph, whose nodes are connected to (or contained in) the hyperedges surrounding the replaced handle by using the eNCE rewriting mechanism. HRNCE grammars can generate all recursively enumerable languages. HRNCE grammars without edge erasing can generate PSPACE-complete languages. Separated HRNCE (S-HRNCE) grammars have many useful normal forms, including Chomsky, Greibach, and context-free normal forms. S-HRNCE languages are in NP and there is an NP-complete linear HRNCE (Lin-HRNCE) language satisfying any two of the following conditions: connected; degree-bounded; and rankbounded. On the other hand, S-HRNCE (Lin-HRNCE) languages satisfying all these three conditions are in LOGCFL (NLOG) and there is such a language which is LOGCFL-complete (NLOG-complete). The equivalence problem is undecidable for Lin-HRNCE languages.
Year
DOI
Venue
1999
10.1016/S0304-3975(99)00258-3
Theor. Comput. Sci.
Keywords
Field
DocType
complexity,graph grammars,normal forms,formal languages,hypergraph generating system,hrnce grammar
Tree-adjoining grammar,Rule-based machine translation,Discrete mathematics,Algebra,Computer science,Hypergraph,Rewriting
Journal
Volume
Issue
ISSN
223
1-2
Theoretical Computer Science
Citations 
PageRank 
References 
5
0.49
24
Authors
2
Name
Order
Citations
PageRank
Changwook Kim110911.88
Tae Eui Jeong260.86