On Language Equations with One-sided Concatenation

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

Abstrakty

EN

Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are EXPTIME-complete.

Słowa kluczowe

EN

computer science; programming languages; equations; Boolean functions; problem solving; decision making; infinite

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 1
• Strony: 1--35
• Opis fizyczny: Bibliogr. 39 poz.

Twórcy

autor

Baader F.

• Institute for Theoretical Computer Science, Technical University of Dresden, Dresden D-01062, Germany

autor

Okhotin A.

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

Bibliografia

• [1]. A. Aiken, D. Kozen, M. Y. Vardi, E. L. Wimmers, “The complexity of set constraints”, Computer Science Logic (CSL 1993, Swansea, UK, September 13-17, 1993), LNCS 832, 1-17.
• [2]. F. Baader, R. Kiisters, “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, P. Narendran, “Unification of concept terms in description logic”, Journal of Symbolic Computation, 31 (2001), 277-305.
• [4]. F. Baader, A. Okhotin, “Solving language equations and disequations with applications to disunification in description logics and monadic set constraints”, Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2012, Merida, Venezuela, March 11-15,2012), LNCS 7180, 107-121.
• [5]. F. Baader and W. Snyder. Unification theory. In Handbook of Automated Reasoning, volume I. Elsevier, 2001.
• [6]. F. Baader, S. Tobies, “The inverse method implements the automata approach for modal satisfiability”, In Proc. IJCAR’01, Springer LNCS 2083, 2001.
• [7]. 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. http: //dx.doi.org/10.1007/s00224-005-1262-y
• [8]. V. G. Bodnarchuk, “Sistemy uravnenii v algebre sobytii” (Systems of equations in the event algebra), in Russian, Zhurnal vychislitel ’noi matematiki i matematicheskoi fiziki (Journal of Computational Mathematics and Mathematical Physics), 3:6 (1963), 1077-1088.
• [9]. W. Buttner. Unification in finite algebras is unitary(?). In Proc. CADE-9, Springer LNCS 310, 1988.
• [10]. W. Charatonik, “Set constraints in some equational theories”, Information and Computation, 142 (1998), 40-75. http://dx.doi.org/10.1006/inco.1997.2692
• [11]. W. Charatonik, L. Pacholski, “Set constraints with projections”, Journal of the ACM, 57:4 (2010), article 23. http://doi.acm.org/10.1145/1734213.1734217
• [12]. J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, 1971.
• [13]. A. E. Frid, “Simple equations on binary factorial languages”, Theoretical Computer Science, 410:30-32 , 2947-2956.
• [14]. S. Ginsburg, H. G. Rice, “Two families of languages related to ALGOL”, Journal of the ACM, 9 (1962), 350-371. http://dx.doi.org/10.1145/321127.321132
• [15]. R. Gilleron, S. Tison, M. Tommasi, “Set constraints and automata”, Information and Computation, 149:1 (1999), 1-41. http://dx.doi.org/10.1006/inco.1998.2747
• [16]. A. JeZ, A. Okhotin, “On the computational completeness of equations over sets of natural numbers”, Automata, Languages and Programming (ICALP 2008, Reykjavik, Iceland, July 6-13, 2008), part II, LNCS 5126, 63-74. http://dx.doi.org/10.1007/978-3-540-70583-3_6
• [17]. A. JeZ, A. Okhotin, “Equations over sets of natural numbers with addition only”, STACS 2009 (Freiburg, Germany, 26-28 February, 2009), 577-588. http: //drops. dagstuhl. de/opus/volltexte/2009/1806
• [18]. M. Kunc, “The power of commuting with finite sets of words”, Theory of Computing Systems, 40:4 (2007), 521-551.
• [19]. 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. http://dx.doi.org/10.1007/ 978-3-540-73208-2_3
• [20]. 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. http://dx.doi.org/10.1007/978-3-642-14455-4_27
• [21]. G. S. Makanin, The problem of solvability of equations in a free semigroup. Math. Sbornik 103:147-236. English translation in Math. USSR Sbornik 32, 1977.
• [22]. W. Martens, M. Niewerth, T. Schwentick, “Schema design for XML repositories: complexity and tractability”, Symposium on Principles of Database Systems (PODS 2010, Indianapolis, USA, June 6-11, 2010), 239-250. http://dx.doi.org/10.1145/1807085.1807117
• [23]. T. Nipkow. Unification in primal algebras, their powers and their varieties. J. of the ACM, 37(1):742-776, 1990.
• [24]. D. Niwinski, “On the cardinality of sets of infinite trees recognizable by finite automata”, Mathematical Foundations of Computer Science (MFCS 1991, Kazimierz Dolny, Poland, September 9-13, 1991), LNCS 520, 1991, 367-376.
• [25]. A. Okhotin, “Conjunctive grammars and systems of language equations”, Programming and Computer Software, 28:5 (2002), 243-249.
• [26]. 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. http://dx.doi.org/10.1007/3-540-45061-0_21
• [27]. A. Okhotin, “Unresolved systems of language equations: expressive power and decision problems”, Theoretical Computer Science, 349:3 (2005), 283-308.
• [28]. 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.
• [29]. A. Okhotin, “Decision problems for language equations”, Journal of Computer and System Sciences, 76:3-4 , 251-266.
• [30]. A. Okhotin, P. Rondogiannis, “On the expressive power of univariate equations over sets of natural numbers”, Information and Computation, 212 (2012), 1-14.
• [31]. A. Okhotin, O. Yakimova, “Language equations with complementation: Decision problems”, Theoretical Computer Science, 376:1-2 (2007), 112-126. http://dx.doi.org/10.1016/j .tcs.2007.01.016
• [32]. 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. http: //dx. doi. org/10. 1137/0214066
• [33]. M. O. Rabin, “Decidability of second-order theories and automata on infinite trees”, Transactions of the American Mathematical Society, 141 (1969), 1-35.
• [34]. A. Salomaa, Theory of Automata, Pergamon Press, Oxford, 1969.
• [35]. H. Seidl, “Haskell overloading is DEXPTIME-complete”, Information Processing Letters, 52(2):57-60, 1994.
• [36]. L. R. Stockmeyer, The Complexity of Decision Problems in Automata Theory and Logic, Ph.D. thesis, Dept. of Electrical Engineering, MIT, 1974.
• [37]. A. Tarski, “A lattice-theoretical fixpoint theorem and its applications”, Pacific Journal of Mathematics, 5 (1955), 285-309.http://projecteuclid.org/euclid.pjm/1103044538
• [38]. W. Thomas. Automata on infinite objects. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 133-191. Elsevier Science Publishers, Amsterdam, 1990.
• [39]. M. Y. Vardi and P. Wolper, “Automata-theoretic techniques for modal logics of programs”, Journal of Computer and System Sciences, 32 (1986), 183-221.