Decision problems for language equations
DOI10.1016/J.JCSS.2009.08.002zbMATH Open1201.68067OpenAlexW2135734455MaRDI QIDQ972384FDOQ972384
Authors: Alexander Okhotin 
Publication date: 25 May 2010
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.08.002
Recommendations
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Automata and formal grammars in connection with logical questions (03D05)
Cites Work
- Reversal-bounded multipushdown machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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?)
- Two Families of Languages Related to ALGOL
- Unification of concept terms in description logics
- On equations for regular languages, finite automata, and sequential networks
- Conjunctive grammars and systems of language equations
- Title not available (Why is that?)
- Language equations, maximality and error-detection
- Conway's problem for three-word sets.
- Closure and decidability properties of some language classes with respect to ciliate bio-operations.
- Title not available (Why is that?)
- The Equivalence Problem of Finite Substitutions on ab*c, with Applications
- Title not available (Why is that?)
- Domain mu-calculus
- Set constraints in some equational theories
Cited In (31)
- Language Equations with Complementation
- On the expressive power of univariate equations over sets of natural numbers
- Solving systems of explicit language relations
- Solving language equations using flanked automata
- Generalized language equations with multiple solutions
- STACS 2004
- Decision problems concerning properties of finite sets of equations
- Equations over sets of integers with addition only
- Mathematical Foundations of Computer Science 2005
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- The Boolean formula value problem as formal language
- Equations between Regular Terms and an Application to Process Logic
- Complexity of equations over sets of natural numbers
- On language decompositions and primality
- Representing hyper-arithmetical sets by equations over sets of integers
- Language equations with complementation: expressive power
- Unresolved systems of language equations: expressive power and decision problems
- Language equations with complementation: decision problems
- Language equations with symmetric difference
- On equations over sets of numbers and their limitations
- Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
- 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?)
- Decidable properties of finite sets of equations in trivial languages
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Title not available (Why is that?)
- Language Equations with Symmetric Difference
- Least and greatest solutions of equations over sets of integers
- A Simple P-Complete Problem and Its Representations by Language Equations
Uses Software
This page was built for publication: Decision problems for language equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972384)
