Language equations with complementation: expressive power
From MaRDI portal
Publication:764318
DOI10.1016/j.tcs.2011.10.003zbMath1279.68168OpenAlexW2026455391MaRDI QIDQ764318
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
Related Items (5)
Equations over sets of integers with addition only ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Ternary Equational Languages ⋮ Language equations
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Well-founded semantics for Boolean grammars
- On the existence of prime decompositions
- Language equations with complementation: decision problems
- Decision problems for language equations
- Conjunctive grammars with restricted disjunction
- Unrestricted complementation in language equations over a one-letter alphabet
- Boolean grammars
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- The dual of concatenation
- Recursive descent parsing for Boolean grammars
- The power of commuting with finite sets of words
- Language Equations with Symmetric Difference
- On the Computational Completeness of Equations over Sets of Natural Numbers
- CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
- Fast Parsing for Boolean Grammars: A Generalization of Valiant’s Algorithm
- On the equivalence of linear conjunctive grammars and trellis automata
- GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
- Two Families of Languages Related to ALGOL
- Unification of concept terms in description logics
This page was built for publication: Language equations with complementation: expressive power
