Unresolved systems of language equations: expressive power and decision problems

DOI10.1016/J.TCS.2005.07.038MaRDI QIDQ817804zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

formal languageslanguage equationsdecision problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• scientific article; zbMATH DE number 2038714
• Decision problems for language equations
• Language Equations with Complementation
• Language equations with complementation: decision problems
• Mathematical Foundations of Computer Science 2005

Cites work

• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2038714 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• Boolean grammars
• Conjunctive grammars and systems of language equations
• Constructive versions of Tarski's fixed point theorems
• Conway's problem for three-word sets.
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision problems for language equations
• Domain mu-calculus
• Maximal and minimal solutions to language equations
• On equations for regular languages, finite automata, and sequential networks
• On the equivalence of linear conjunctive grammars and trellis automata
• Polynomial operations and hierarchies of concatenation
• Reversal-bounded multipushdown machines
• STACS 2005
• Systolic trellis automatata †
• Two Families of Languages Related to ALGOL
• Unification of concept terms in description logics
• Unrestricted complementation in language equations over a one-letter alphabet

Cited in

(20)

• Language equations with complementation: decision problems
• scientific article; zbMATH DE number 2038714 (Why is no real title available?)
• Machines, Computations, and Universality
• Language equations with complementation: expressive power
• Language Equations with Complementation
• Complexity of equations over sets of natural numbers
• Language equations
• Computational completeness of equations over sets of natural numbers
• Solving language equations and disequations with applications to disunification in description logics and monadic set constraints
• Mathematical Foundations of Computer Science 2005
• Language Equations with Symmetric Difference
• The dual of concatenation
• On equations over sets of numbers and their limitations
• Decision problems for language equations
• Representing hyper-arithmetical sets by equations over sets of integers
• On Remainder Equations
• Equations over sets of integers with addition only
• Solving systems of explicit language relations
• Conjunctive grammars and equations over sets of natural numbers
• On Equations over Sets of Numbers and Their Limitations

Describes a project that uses

Uses Software

• ALGOL 60

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)