Algebraic properties of structured context-free languages: old approaches and novel developments

Computer Science – Formal Languages and Automata Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Extended version of paper presented at WORDS2009, Salerno,Italy, September 2009

Scientific paper

The historical research line on the algebraic properties of structured CF languages initiated by McNaughton's Parenthesis Languages has recently attracted much renewed interest with the Balanced Languages, the Visibly Pushdown Automata languages (VPDA), the Synchronized Languages, and the Height-deterministic ones. Such families preserve to a varying degree the basic algebraic properties of Regular languages: boolean closure, closure under reversal, under concatenation, and Kleene star. We prove that the VPDA family is strictly contained within the Floyd Grammars (FG) family historically known as operator precedence. Languages over the same precedence matrix are known to be closed under boolean operations, and are recognized by a machine whose pop or push operations on the stack are purely determined by terminal letters. We characterize VPDA's as the subclass of FG having a peculiarly structured set of precedence relations, and balanced grammars as a further restricted case. The non-counting invariance property of FG has a direct implication for VPDA too.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Algebraic properties of structured context-free languages: old approaches and novel developments 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 Algebraic properties of structured context-free languages: old approaches and novel developments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic properties of structured context-free languages: old approaches and novel developments will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-100644

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.