Publication:693054

DOI10.1007/s00224-011-9352-5zbMath1279.68158OpenAlexW3101545656MaRDI QIDQ693054

Artur Jeż, Alexander Okhotin

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9352-5

zbMATH Keywords

computabilityarithmetical hierarchylanguage equationshyper-arithmetical hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Equations over sets of integers with addition only, Conjunctive and Boolean grammars: the true general case of the context-free grammars, Computable fixpoints in well-structured symbolic model checking, Computational completeness of equations over sets of natural numbers, Least and greatest solutions of equations over sets of integers, Language equations

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the expressive power of univariate equations over sets of natural numbers
• Complexity of equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• Unresolved systems of language equations: expressive power and decision problems
• The complexity of membership problems for circuits over sets of integers
• Decision problems for language equations
• Elementary induction on abstract structures
• The finite power property in free groups
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• The power of commuting with finite sets of words
• ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS
• On the Computational Completeness of Equations over Sets of Natural Numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• On Language Equations XXK = XXL and XM = N over a Unary Alphabet
• Least and Greatest Solutions of Equations over Sets of Integers
• Presburger arithmetic with unary predicates is Π₁¹ complete
• An introduction to hyperarithmetical functions
• Two Families of Languages Related to ALGOL