IJPAM: Volume 59, No. 3 (2010)

PARALLEL CONTEXT-FREE STRING-TOKEN PETRI NETS

D.K. Shirley Gloria$^1$32, Bharathiyar Street, Ananthapuram, East Tambaram, Chennai, 600 059, TN, INDIA, Beulah Immanuel$^2$, K. Rangarajan$^3$
$^1$Sathyabama University
Jeppiaar Nagar, Chennai-119, TN, INDIA
e-mail: [email protected]
$^2$ Department of Mathematics
Women's Christian College
Chennai-6, TN, INDIA
e-mail: [email protected]
$^3$MCA Department
Bharath University
Selaiyur, Chennai-73, TN, INDIA
e-mail: [email protected]


Abstract.Parallel context-free languages are generated by parallel context-free grammars. We have proved that every parallel context free languages can be generated by string-token Petri net. We have constructed string token Petri nets to accept the union and concatenation of family of parallel context-free languages. It is also proved that the family of parallel context-free languages is contained in the family of context sensitive languages.

Received: January 4, 2010

AMS Subject Classification: 03H10, 90A16, 26A33

Key Words and Phrases: string-token Petri net (STPN), context-free languages (CFL), parallel context free languages (PCL), linear bounded automaton (lba), context sensitive languages (CSL)

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2010
Volume: 59
Issue: 3