Generating All Permutations by Context-Free Grammars in Chomsky Normal Form

P.R.J. Asveld

Generating All Permutations by Context-Free Grammars in Chomsky Normal Form

P.R.J. Asveld

Research output: Book/Report › Report › Professional

1 Downloads (Pure)

Abstract

Let $L_n$ be the finite language of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). We consider context-free grammars $G_n$ in Chomsky normal form that generate $L_n$. In particular we study a few families $\{G_n\}_{n\geq1}$, satisfying $L(G_n)=L_n$ for $n\geq 1$, with respect to their descriptional complexity, i.e.\ we determine the number of nonterminal symbols and the number of production rules of $G_n$ as functions of $n$.

Original language	Undefined
Place of Publication	Enschede
Publisher	Centre for Telematics and Information Technology (CTIT)
Number of pages	19
Publication status	Published - Dec 2004

Publication series

Name	CTIT TR-04
Publisher	University of Twente, Centre for Telematics and Information Technology (CTIT)
No.	50
ISSN (Print)	1381-3625

Keywords

EWI-5756
METIS-221470
IR-63051

Access to Document

http://eprints.eemcs.utwente.nl/secure2/5756/01/gap.pdf

Cite this

@book{dd42d5530a1c4f28b66d5df93348b34c,

title = "Generating All Permutations by Context-Free Grammars in Chomsky Normal Form",

abstract = "Let \$L\_n\$ be the finite language of all \$n!\$ strings that are permutations of \$n\$ different symbols (\$n\textbackslash{}geq 1\$). We consider context-free grammars \$G\_n\$ in Chomsky normal form that generate \$L\_n\$. In particular we study a few families \$\textbackslash{}\{G\_n\textbackslash{}\}\_\{n\textbackslash{}geq1\}\$, satisfying \$L(G\_n)=L\_n\$ for \$n\textbackslash{}geq 1\$, with respect to their descriptional complexity, i.e.\textbackslash{} we determine the number of nonterminal symbols and the number of production rules of \$G\_n\$ as functions of \$n\$.",

keywords = "EWI-5756, METIS-221470, IR-63051",

author = "P.R.J. Asveld",

note = "Imported from CTIT",

year = "2004",

month = dec,

language = "Undefined",

series = "CTIT TR-04",

publisher = "Centre for Telematics and Information Technology (CTIT)",

number = "50",

address = "Netherlands",

}

TY - BOOK

T1 - Generating All Permutations by Context-Free Grammars in Chomsky Normal Form

AU - Asveld, P.R.J.

N1 - Imported from CTIT

PY - 2004/12

Y1 - 2004/12

N2 - Let $L_n$ be the finite language of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). We consider context-free grammars $G_n$ in Chomsky normal form that generate $L_n$. In particular we study a few families $\{G_n\}_{n\geq1}$, satisfying $L(G_n)=L_n$ for $n\geq 1$, with respect to their descriptional complexity, i.e.\ we determine the number of nonterminal symbols and the number of production rules of $G_n$ as functions of $n$.

AB - Let $L_n$ be the finite language of all $n!$ strings that are permutations of $n$ different symbols ($n\geq 1$). We consider context-free grammars $G_n$ in Chomsky normal form that generate $L_n$. In particular we study a few families $\{G_n\}_{n\geq1}$, satisfying $L(G_n)=L_n$ for $n\geq 1$, with respect to their descriptional complexity, i.e.\ we determine the number of nonterminal symbols and the number of production rules of $G_n$ as functions of $n$.

KW - EWI-5756

KW - METIS-221470

KW - IR-63051

M3 - Report

T3 - CTIT TR-04

BT - Generating All Permutations by Context-Free Grammars in Chomsky Normal Form

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -