Toward a Compositional Theory of Leftist Grammars and Transformations

Details Toward a Compositional Theory of Leftist Grammars and Transformations Toward a Compositional Theory of Leftist Grammars and Transformations

2010-01-27

arxiv.org/abs/1001.5047v1

Proc. FoSSaCS'10, LNCS 6014, pages 237-251. Springer, 2010

Computer Science

Formal Languages and Automata Theory

Full version of the FOSSACS 2010 paper

Scientific paper

10.1007/978-3-642-12032-9_17

Leftist grammars [Motwani et al., STOC 2000] are special semi-Thue systems where symbols can only insert or erase to their left. We develop a theory of leftist grammars seen as word transformers as a tool toward rigorous analyses of their computational power. Our main contributions in this first paper are (1) constructions proving that leftist transformations are closed under compositions and transitive closures, and (2) a proof that bounded reachability is NP-complete even for leftist grammars with acyclic rules.

Affiliated with

Also associated with

No associations

Rating

Toward a Compositional Theory of Leftist Grammars and Transformations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Toward a Compositional Theory of Leftist Grammars and Transformations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Toward a Compositional Theory of Leftist Grammars and Transformations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-253776