Language Equations with Symmetric Difference

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

Abstrakty

EN

The paper investigates the expressive power of language equations with the operations of concatenation and symmetric difference. For equations over every finite alphabet Σ with |Σ| ≥1, it is demonstrated that the sets representable by unique solutions of such equations are exactly the recursive sets over , and the sets representable by their least (greatest) solutions are exactly the recursively enumerable sets (their complements, respectively). If |Σ| ≥ 2, the same characterization holds already for equations using symmetric difference and linear concatenation with regular constants. In both cases, the solution existence problem is Π (0,1)-complete, the existence of a unique, a least or a greatest solution is Π(0,2)-complete, while the existence of finitely many solutions is Σ(0,3)-complete.

Słowa kluczowe

EN

language equations; symmetric difference

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 205-222
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Okhotin, A.

• Department of Mathematics, University of Turku Turku FI-20014, Finland,

Bibliografia

• [1] J. Autebert, J. Berstel, L. Boasson, "Context-free languages and pushdown automata", in: Rozenberg, Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, Berlin, 1997, 111-174.
• [2] F. Baader, R. Küsters, "Unification in a description logic with transitive closure of roles", Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2001, Havana, Cuba, December 3-7, 2001), LNCS 2250, 217-232.
• [3] F. Baader, A. Okhotin, "Complexity of language equations with one-sided concatenation and all Boolean operations", 20th International Workshop on Unification (UNIF 2006, Seattle, USA, August 11, 2006), 59-73.
• [4] B. S. Baker, R. V. Book, "Reversal-bounded multipushdown machines", Journal of Computer and System Sciences, 8 (1974), 315-332.
• [5] S. Bala, "Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms", Theory of Computing Systems, 39:1 (2006), 137-163.
• [6] S. Ginsburg, H. G. Rice, "Two families of languages related to ALGOL", Journal of the ACM, 9 (1962), 350-371.
• [7] J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings of Symposia in Applied Mathematics, Vol. 19, AMS, 1967, 42-51.
• [8] A. Jeż, "Conjunctive grammars can generate non-regular unary languages", International Journal of Foundations of Computer Science, 19:3 (2008), 597-615.
• [9] A. Jeż, A. Okhotin, "Conjunctive grammars over a unary alphabet: undecidability and unbounded growth", Theory of Computing Systems, 46:1 (2010), 27-58.
• [10] 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.
• [11] A. Jeż, A. Okhotin, "Equations over sets of natural numbers with addition only", STACS 2009 (Freiburg, Germany, 26-28 February, 2009), 577-588.
• [12] A. J. Korenjak, J. E. Hopcroft, "Simple deterministic languages", 7th Annual Symposium on Switching and Automata Theory (SWAT 1966, Berkeley, USA, October 23-25, 1966), 36-46.
• [13] M. Kunc, "Regular solutions of language inequalities and well quasi-orders", Theoretical Computer Science, 348:2-3 (2005), 277-293.
• [14] M. Kunc, "The power of commuting with finite sets of words", Theory of Computing Systems, 40:4 (2007), 521-551.
• [15] T. Lehtinen, A. Okhotin, "On equations over sets of numbers and their limitations", International Journal of Foundations of Computer Science, 22:2 (2011), 377-393.
• [16] T. Lehtinen, A. Okhotin, "On language equations XXK = XXL and XM = N over a unary alphabet", Developments in Language Theory (DLT 2010, London, Ontario, Canada, 17-20 August 2010), LNCS 6224, 291-302.
• [17] W. Martens, M. Niewerth, T. Schwentick, "Schema design for XML repositories: complexity and tractability", PODS 2010 (Indianapolis, USA, June 6-11, 2010), 239-250.
• [18] A. R. Meyer, A. M. Rabinovich, "Valid identity problem for shuffle regular expressions", Journal of Automata, Languages and Combinatorics 7:1 (2002), 109-125.
• [19] A. Okhotin, "Conjunctive grammars and systems of language equations", Programming and Computer Software, 28:5 (2002), 243-249.
• [20] A. Okhotin, "Decision problems for language equations with Boolean operations", Automata, Languages and Programming (ICALP 2003, Eindhoven, The Netherlands, 30 June-4 July 2003), LNCS 2719, 239-251.
• [21] A. Okhotin, "Boolean grammars", Information and Computation, 194:1 (2004), 19-48.
• [22] A. Okhotin, "The dual of concatenation", Theoretical Computer Science, 345:2-3 (2005), 425-447.
• [23] A. Okhotin, "Unresolved systems of language equations: expressive power and decision problems", Theoretical Computer Science, 349:3 (2005), 283-308.
• [24] A. Okhotin, "Strict language inequalities and their decision problems", Mathematical Foundations of Computer Science (MFCS 2005, Gdansk, Poland, August 29-September 2, 2005), LNCS 3618, 708-719.
• [25] A. Okhotin, "Seven families of language equations", AutoMathA 2007, Palermo, Italy, June 18-22, 2007.
• [26] A. Okhotin, "Decision problems for language equations", Journal of Computer and System Sciences, 76:3-4 (2010), 251-266.
• [27] A. Okhotin, O. Yakimova, "Language equations with complementation: Decision problems", Theoretical Computer Science, 376:1-2 (2007), 112-126.
• [28] A. Okhotin, O. Yakimova, "Language equations with complementation: Expressive power", Theoretical Computer Science, 416 (2012), 71-86.
• [29] R. Parikh, A. Chandra, J. Halpern, A. Meyer, "Equations between regular terms and an application to process logic", SIAM Journal on Computing, 14:4 (1985), 935-942.
• [30] E. L. Post, The Two-Valued Iterative Systems of Mathematical Logic, Princeton University Press, 1941.
• [31] S. V. Yablonski, G. P. Gavrilov, V. B. Kudryavtsev, Funktsii algebry logiki i klassy Posta (Functions of logic algebra and the classes of Post), Moscow, 1966, in Russian.