Least and greatest solutions of equations over sets of integers

DOI10.1016/j.tcs.2016.01.013zbMath1335.68126OpenAlexW2249273004MaRDI QIDQ5964016

Artur Jeż, Alexander Okhotin

Publication date: 26 February 2016

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

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

zbMATH Keywords

computabilityanalytical hierarchylanguage equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Complexity of equations over sets of natural numbers
• Representing hyper-arithmetical sets by equations over sets of integers
• The complexity of membership problems for circuits over sets of integers
• Decision problems for language equations
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Computational completeness of equations over sets of natural numbers
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• Theory of computation.
• A lattice-theoretical fixpoint theorem and its applications
• Equations X + A = B and (X + X) + C = (X − X) + D over Sets of Natural Numbers
• ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• On Language Equations XXK = XXL and XM = N over a Unary Alphabet
• On the equivalence of linear conjunctive grammars and trellis automata
• Mathematical Foundations of Computer Science 2005
• Two Families of Languages Related to ALGOL

This page was built for publication: Least and greatest solutions of equations over sets of integers