Language equations with complementation: decision problems
From MaRDI portal
Publication:880178
DOI10.1016/j.tcs.2007.01.016zbMath1111.68062MaRDI QIDQ880178
Alexander Okhotin, Oksana S. Yakimova
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
68Q45: Formal languages and automata
68Q42: Grammars and rewriting systems
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Uses Software
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