Grammar Logics in Nested Sequent Calculus: Proof Theory and Decision Procedures

Computer Science – Logic in Computer Science

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

A grammar logic refers to an extension to the multi-modal logic K in which the modal axioms are generated from a formal grammar. We consider a proof theory, in nested sequent calculus, of grammar logics with converse, i.e., every modal operator [a] comes with a converse. Extending previous works on nested sequent systems for tense logics, we show all grammar logics (with or without converse) can be formalised in nested sequent calculi, where the axioms are internalised in the calculi as structural rules. Syntactic cut-elimination for these calculi is proved using a procedure similar to that for display logics. If the grammar is context-free, then one can get rid of all structural rules, in favor of deep inference and additional propagation rules. We give a novel semi-decision procedure for context-free grammar logics, using nested sequent calculus with deep inference, and show that, in the case where the given context-free grammar is regular, this procedure terminates. Unlike all other existing decision procedures for regular grammar logics in the literature, our procedure does not assume that a finite state automaton encoding the axioms is given.

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

Grammar Logics in Nested Sequent Calculus: Proof Theory and Decision Procedures 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 Grammar Logics in Nested Sequent Calculus: Proof Theory and Decision Procedures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grammar Logics in Nested Sequent Calculus: Proof Theory and Decision Procedures will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-717002

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