Boolean Grammars

  • Alexander Okhotin
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


As a direct continuation of the earlier research on conjunctive grammars — context-free grammars equipped with intersection — this paper introduces a new class of formal grammars, which allow the use of all set-theoretic operations as an integral part of the formalism of rules. Rigorous semantics for such grammars is defined by language equations in a way that allows to generalize some techniques from the theory of context-free grammars, including Chomsky normal form, Cocke—Kasami—Younger recognition algorithm and some limited extension of the notion of a parse tree, which together allow to conjecture the practical applicability of the new concept.


Normal Form Parse Tree Input String Formal Grammar Boolean Vector 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    J. Autebert, J. Berstel and L. Boasson, “Context-Free Languages and Pushdown Automata”, Handbook of Formal Languages, Vol. 1, 111–174, Springer-Verlag, Berlin, 1997.Google Scholar
  2. 2.
    K. Culik II, J. Gruska, A. Salomaa, “Systolic trellis automata”, I and II, Internat. Journal of Computer Mathematics, 15 (1984), 195–212, and 16 (1984), 3–22.zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    E.L. Leiss, Language equations, Springer-Verlag, New York, 1999.zbMATHGoogle Scholar
  4. 4.
    A. Okhotin, “Conjunctive grammars”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519–535.zbMATHMathSciNetGoogle Scholar
  5. 5.
    A. Okhotin, “Conjunctive grammars and systems of language equations”, Programming and Computer Software, 28:5 (2002), 243–249.zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    A. Okhotin, “Automaton representation of linear conjunctive languages”, Developments in Language Theory (Proceedings of DLT 2002), LNCS, to appear.Google Scholar
  7. 7.
    A. Okhotin, “Whale Calf, a parser generator for conjunctive grammars”, Implementation and Application of Automata (Proc. of CIAA 2002), LNCS, to appear; the software is available at, Scholar
  8. 8.
    A. Okhotin, “Decision problems for language equations with Boolean operations”, Proceedings of ICALP 2003, LNCS, to appear.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Alexander Okhotin
    • 1
  1. 1.School of ComputingQueen’s UniversityKingstonCanada

Personalised recommendations