Name
Abstract | ||
|---|---|---|
Synchronized context-free grammars are special context-free grammars together with a relation which must be satisfied between every pair of paths from root to leaf in a derivation tree, in order to contribute towards the generated language. In the past, only the equality relation and the prefix relation have been studied, with both methods generating exactly the ET0L languages. In this paper, we study arbitrary relations, and in particular, those defined by a transducer. We show that if we use arbitrary a-transducers, we can generate all recursively enumerable languages, and moreover, there exists a single fixed transducer, even over a two letter alphabet, which allows to generate all recursively enumerable languages. We also study the problem over unary transducers. Although it is left open whether or not we can generate all recursively enumerable languages with unary transducers, we are able to demonstrate that we can generate all ET0L languages as well as a language that is not an indexed language. Only by varying the transducer used to define the relation, this generalization is natural, and can give each of the following language families: context-free languages, a family between the E0L and ET0L languages, ET0L languages, and recursively enumerable languages. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-31653-1_11 | Developments in Language Theory |
Keywords | Field | DocType |
single fixed transducer,prefix relation,recursively enumerable language,generalized derivation,following language family,equality relation,et0l language,arbitrary relation,unary transducers,context-free language,synchronized context-free grammar | Context-sensitive grammar,Discrete mathematics,Maximal set,Algebra,Recursively enumerable set,Computer science,Abstract family of languages,Recursively enumerable language,Indexed language,Cone (formal languages),Unrestricted grammar | Conference |
Volume | ISSN | Citations |
7410 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Markus Holzer | 1 | 192 | 22.14 |
| Sebastian Jakobi | 2 | 45 | 10.67 |
| Ian McQuillan | 3 | 97 | 24.72 |