Unresolved systems of language equations: expressive power and decision problems
From MaRDI portal
Publication:817804
DOI10.1016/J.TCS.2005.07.038zbMATH Open1086.68077OpenAlexW2070863577MaRDI QIDQ817804FDOQ817804
Authors: Alexander Okhotin 
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.038
Recommendations
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Reversal-bounded multipushdown machines
- Constructive versions of Tarski's fixed point theorems
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Maximal and minimal solutions to language equations
- Unrestricted complementation in language equations over a one-letter alphabet
- Boolean grammars
- Title not available (Why is that?)
- On the equivalence of linear conjunctive grammars and trellis automata
- Two Families of Languages Related to ALGOL
- Decision problems for language equations
- Unification of concept terms in description logics
- On equations for regular languages, finite automata, and sequential networks
- Conjunctive grammars and systems of language equations
- Systolic trellis automatata †
- Title not available (Why is that?)
- Conway's problem for three-word sets.
- Title not available (Why is that?)
- Polynomial operations and hierarchies of concatenation
- Title not available (Why is that?)
- Domain mu-calculus
- STACS 2005
Cited In (20)
- Language Equations with Complementation
- Solving systems of explicit language relations
- Conjunctive grammars and equations over sets of natural numbers
- Equations over sets of integers with addition only
- Mathematical Foundations of Computer Science 2005
- On Remainder Equations
- Complexity of equations over sets of natural numbers
- Representing hyper-arithmetical sets by equations over sets of integers
- Language equations with complementation: expressive power
- Language equations with complementation: decision problems
- Decision problems for language equations
- The dual of concatenation
- Machines, Computations, and Universality
- On equations over sets of numbers and their limitations
- Language equations
- Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
- Computational completeness of equations over sets of natural numbers
- Title not available (Why is that?)
- Language Equations with Symmetric Difference
- On Equations over Sets of Numbers and Their Limitations
Uses Software
This page was built for publication: Unresolved systems of language equations: expressive power and decision problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817804)
