Univariate Equations Over Sets of Natural Numbers

• Autorzy: Jeż A. , Okhotin A.
• Języki publikacji: EN

Abstrakty

EN

It is shown that equations of the form φ(X) = ψ(X), in which the unknown X is a set of natural numbers and φ, ψ use the operations of union, intersection and addition of sets S + T = {m + n | m ∈ S, n ∈T}, can simulate systems of equations φ(X1, . . . ,Xn) = φ(X1, . . . ,Xn) with 1 ≤ j ≤ l, in the sense that solutions of any such system are encoded in the solutions of the corresponding equation. This implies computational universality of least and greatest solutions of equations φ(X) = ψ(X), as well as undecidability of their basic decision problems. It is sufficient to use only singleton constants in the construction. All results equally apply to language equations over a one-letter alphabet Σ = {α}.

Słowa kluczowe

EN

language equations; unary alphabet; univariate equations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 4
• Strony: 329--348
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Jeż A.

autor

Okhotin A.

• Institute of Computer Science, University of Wrocław, 50–383 Wrocław, Poland,

Bibliografia

• [1] S. Ginsburg, H. G. Rice, "Two families of languages related to ALGOL", Journal of the ACM, 9 (1962), 350-371.
• [2] A. Jeż, "Conjunctive grammars can generate non-regular unary languages", International Journal of Foundations of Computer Science, 19:3 (2008), 597-615.
• [3] A. Jeż, A. Okhotin, "Conjunctive grammars over a unary alphabet: undecidability and unbounded growth", Theory of Computing Systems, 46:1 (2010), 27-58.
• [4] A. Jeż, A. Okhotin, "On the computational completeness of equations over sets of natural numbers" 35th International Colloquium on Automata, Languages and Programming (ICALP 2008, Reykjavik, Iceland, July 7-11, 2008), 63-74.
• [5] A. Jeż, A. Okhotin, "One-nonterminal conjunctive grammars over a unary alphabet", Computer Science inRussia (CSR 2009, Novosibirsk, Russia, 18-23 August, 2009), LNCS 5675, 191-202.
• [6] M. Kunc, "What do we know about language equations?", Developments in Language Theory (DLT 2007,Turku, Finland, July 3-6, 2007), LNCS 4588, 23-27.
• [7] P. McKenzie, K. W. Wagner, "The complexity of membership problems for circuits over sets of natural numbers", Computational Complexity, 16 (2007), 211-244.
• [8] A. Okhotin, "Conjunctive grammars", Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535.
• [9] A. Okhotin, "Conjunctive grammars and systems of language equations", Programming and Computer Software,28 (2002), 243-249.
• [10] A. Okhotin, "Unresolved systems of language equations: expressive power and decision problems", TheoreticalComputer Science, 349:3 (2005), 283-308.
• [11] A. Okhotin, "Strict language inequalities and their decision problems", Mathematical Foundations of Computer Science (MFCS 2005, Gda´nsk, Poland, August 29-September 2, 2005), LNCS 3618, 708-719.
• [12] A. Okhotin, "Computational universality in one-variable language equations", Fundamenta Informaticae, 74:4 (2006), 563-578.
• [13] A. Okhotin, "Nine open problems for conjunctive and Boolean grammars", Bulletin of the EATCS, 91 (2007), 96-119.
• [14] A. Okhotin, "Decision problems for language equations", Journal of Computer and System Sciences, 76:3-4 (2010), 251-266.
• [15] A. Okhotin, P. Rondogiannis, "On the expressive power of univariate equations over sets of natural numbers", IFIP International Conference on Theoretical Computer Science (TCS 2008, Milan, Italy, 8-10 September, 2008), IFIP vol. 273, 215-227.
• [16] L. J. Stockmeyer, A. R. Meyer, "Word problems requiring exponential time", STOC 1973, 1-9.