Language equations with complementation: expressive power

DOI10.1016/J.TCS.2011.10.003zbMATH Open1279.68168OpenAlexW2026455391MaRDI QIDQ764318FDOQ764318

Alexander Okhotin, Oksana S. Yakimova

Publication date: 13 March 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.10.003

zbMATH Keywords

context-free grammarsnegationlanguage equationsBoolean grammarscomplementation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The power of commuting with finite sets of words
• Unrestricted complementation in language equations over a one-letter alphabet
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL
• Language equations with complementation: decision problems
• Decision problems for language equations
• On the decomposition of finite languages
• Recursive descent parsing for Boolean grammars
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• Unification of concept terms in description logics
• Well-founded semantics for Boolean grammars
• The dual of concatenation
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
• Conjunctive grammars with restricted disjunction
• On the existence of prime decompositions
• Language Equations with Symmetric Difference

Cited In (8)

• On the expressive power of univariate equations over sets of natural numbers
• Equations over sets of integers with addition only
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Language equations with complementation: decision problems
• On the expressibility of languages by word equations with a bounded number of variables
• Unrestricted complementation in language equations over a one-letter alphabet
• Ternary Equational Languages
• Language equations

Uses Software

• ALGOL 60

This page was built for publication: Language equations with complementation: expressive power

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764318)