Language equations with complementation: expressive power

DOI10.1016/J.TCS.2011.10.003MaRDI QIDQ764318zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Language Equations with Complementation
• Language equations with complementation: decision problems
• On language equations with concatenation and various sets of Boolean operations
• Language equations with symmetric difference
• Unresolved systems of language equations: expressive power and decision problems

Cites work

• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 2162119 (Why is no real title available?)
• Boolean grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• Conjunctive grammars with restricted disjunction
• Decision problems for language equations
• Equations over sets of natural numbers with addition only
• Fast parsing for Boolean grammars: a generalization of Valiant's algorithm
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• Language Equations with Symmetric Difference
• Language equations with complementation: decision problems
• On the Computational Completeness of Equations over Sets of Natural Numbers
• On the decomposition of finite languages
• On the equivalence of linear conjunctive grammars and trellis automata
• On the existence of prime decompositions
• Recursive descent parsing for Boolean grammars
• The dual of concatenation
• The power of commuting with finite sets of words
• Two Families of Languages Related to ALGOL
• Unification of concept terms in description logics
• Unrestricted complementation in language equations over a one-letter alphabet
• Well-founded semantics for Boolean grammars

Cited in

(12)

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

Describes a project that uses

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)