Language equations with complementation: decision problems

DOI10.1016/j.tcs.2007.01.016zbMath1111.68062OpenAlexW1998081523MaRDI QIDQ880178

Oksana S. Yakimova, Alexander Okhotin

Publication date: 11 May 2007

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

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

zbMATH Keywords

computational complexitydecision problemscomplementationnegationlanguage equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

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 ⋮ ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS ⋮ Language equations with complementation: expressive power ⋮ Language equations

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unresolved systems of language equations: expressive power and decision problems
• Set constraints in some equational theories
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Boolean grammars
• The dual of concatenation
• Unification in a Description Logic with Transitive Closure of Roles
• On the unique satisfiability problem
• STACS 2004
• Developments in Language Theory
• Two Families of Languages Related to ALGOL
• STACS 2005
• Unification of concept terms in description logics

This page was built for publication: Language equations with complementation: decision problems