{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T16:10:42Z","timestamp":1653581442267},"reference-count":48,"publisher":"EDP Sciences","issue":"3","funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["118540","134860","257857"],"award-info":[{"award-number":["118540","134860","257857"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[2015,7]]},"DOI":"10.1051\/ita\/2015006","type":"journal-article","created":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T07:52:13Z","timestamp":1447919533000},"page":"205-232","source":"Crossref","is-referenced-by-count":0,"title":["On language equations with concatenation and various sets of Boolean operations"],"prefix":"10.1051","volume":"49","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2015,11,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"J. Autebert, J. Berstel and L. Boasson, Context-free languages and pushdown automata. In vol. 1 ofHandbook of Formal Languages, edited by Rozenberg, Salomaa. Springer\u2013Verlag (1997) 111\u2013174.","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"F. Baader and R. K\u00fcsters, Unification in a description logic with transitive closure of roles, Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2001, Havana, Cuba. Vol. 2250 ofLect. Notes Comput. Sci.(2001) 217\u2013232.","DOI":"10.1007\/3-540-45653-8_15"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Baader F. and Narendran P., Unification of concept terms in description logic.J. Symbolic Comput.31(2001) 277\u2013305.","DOI":"10.1006\/jsco.2000.0426"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"F. Baader and 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, M\u00e9rida, Venezuela. Vol. 7180 ofLect. Notes Comput. Sci.(2012) 107\u2013121.","DOI":"10.1007\/978-3-642-28717-6_11"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Baader F. and Okhotin A., On language equations with one-sided concatenation.Fundamenta Informaticae126(2013) 1\u201335.","DOI":"10.3233\/FI-2013-870"},{"key":"R6","unstructured":"Bala S., Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms.Theory Comput. Syst.39(2006) 137\u2013163."},{"key":"R7","unstructured":"Brzozowski J.A. and Leiss E.L., On equations for regular languages, finite automata, and sequential networks.Theoret Comput. Sci.10(1980) 19\u201335."},{"key":"R8","unstructured":"Domaratzki M. and Salomaa K., Decidability of trajectory-based equations.Theoret. Comput. Sci.345(2005) 304\u2013330."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Ginsburg S. and Rice H.G., Two families of languages related to ALGOL.J. ACM9(1962) 350\u2013371.","DOI":"10.1145\/321127.321132"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Je\u017c A., Conjunctive grammars can generate non-regular unary languages.Int. J. Found. Comput. Sci.19(2008) 597\u2013615.","DOI":"10.1142\/S012905410800584X"},{"key":"R11","unstructured":"A. Je\u017c and A. Okhotin, Equations over sets of natural numbers with addition only. InProc. of 26th Annual Symposium on Theoretical Aspects of Computer Science, Dagstuhl Seminar Proceedings 09001, STACS 2009, Freiburg, Germany, 26\u201328 February(2009) 577\u2013588."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Je\u017c A. and Okhotin A., Conjunctive grammars over a unary alphabet: undecidability and unbounded growth.Theory Comput. Syst.46(2010) 27\u201358.","DOI":"10.1007\/s00224-008-9139-5"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"A. Je\u017c and A. Okhotin, Least and greatest solutions of equations over sets of integers. InProc. of Mathematical Foundations of Computer Science, MFCS 2010, Brno, Czech Republic. Vol. 6281 ofLect. Notes Comput. Sci.(2010) 441\u2013452.","DOI":"10.1007\/978-3-642-15155-2_39"},{"key":"R14","unstructured":"Je\u017c A. and Okhotin A., Complexity of equations over sets of natural numbers.Theory Comput. Syst.48(2011) 319\u2013342."},{"key":"R15","unstructured":"Je\u017c A. and Okhotin A., One-nonterminal conjunctive grammars over a unary alphabet.Theory Comput. Syst.49(2011) 319\u2013342."},{"key":"R16","unstructured":"Je\u017c A. and Okhotin A., Representing hyper-arithmetical sets by equations over sets of integers.Theory Comput. Syst.51(2012) 196\u2013228."},{"key":"R17","unstructured":"Je\u017c A. and Okhotin A., Computational completeness of equations over sets of natural numbers.Inform. Comput.237(2014) 56\u201394."},{"key":"R18","unstructured":"Kari L., On language equations with invertible operations.Theoret Comput. Sci.132(1994) 129\u2013150."},{"key":"R19","unstructured":"Kountouriotis V., Nomikos Ch. and Rondogiannis P., Well-founded semantics for Boolean grammars.Inform. Comput.207(2009) 945\u2013967."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. Kunc, On language inequalitiesXK\u2286LX. InProc. of Developments in Language Theory, DLT 2005, Palermo, Italy. Vol. 3572 ofLect. Notes Comput. Sci.(2005) 327\u2013337.","DOI":"10.1007\/11505877_29"},{"key":"R21","unstructured":"Kunc M., The power of commuting with finite sets of words.Theory Comput. Syst.40(2007) 521\u2013551."},{"key":"R22","unstructured":"D. Lau, Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory. Springer (2006)."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"T. Lehtinen, EquationsX+A=Band (X+X) +C= (X\u2212X) +Dover sets of natural numbers. InProc. of Mathematical Foundations of Computer Science, MFCS 2012, Bratislava, Slovakia, 27\u201331 August. In vol. 7464 ofLect. Notes Comput. Sci.(2012) 615\u2013629.","DOI":"10.1007\/978-3-642-32589-2_54"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"T. Lehtinen and A. Okhotin, On language equationsXXK=XXLandXM=Nover a unary alphabet. InProc. of Developments in Language Theory, DLT 2010, London, Ontario, Canada. Vol. 6224 ofLect. Notes Comput. Sci.(2010) 291\u2013302.","DOI":"10.1007\/978-3-642-14455-4_27"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Lehtinen T. and Okhotin A., On equations over sets of numbers and their limitations.Int. J. Found. Comput. Sci.22(2011) 377\u2013393.","DOI":"10.1142\/S012905411100809X"},{"key":"R26","unstructured":"Leiss E.L., Unrestricted complementation in language equations over a one-letter alphabet.Theoret. Comput. Sci.132(1994) 71\u201393."},{"key":"R27","unstructured":"W. Martens, M. Niewerth and T. Schwentick, Schema design for XML repositories: complexity and tractability, PODS 2010, Indianapolis, USA (2010) 239\u2013250."},{"key":"R28","unstructured":"Okhotin A., Conjunctive grammars.J. Automata, Languages and Combinatorics6(2001) 519\u2013535."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Okhotin A., Conjunctive grammars and systems of language equations.Program. Comput. Softw.28(2002) 243\u2013249.","DOI":"10.1023\/A:1020213411126"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"A. Okhotin, Decision problems for language equations with Boolean operations. InProc. of Automata, Languages and Programming, ICALP 2003, Eindhoven, The Netherlands. Vol. 2719 ofLect. Notes Comput. Sci.(2003) 239\u2013251.","DOI":"10.1007\/3-540-45061-0_21"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"Okhotin A., Boolean grammars.Inform. Comput.194(2004) 19\u201348.","DOI":"10.1016\/j.ic.2004.03.006"},{"key":"R32","unstructured":"Okhotin A., Unresolved systems of language equations: expressive power and decision problems.Theoret. Comput. Sci.349(2005) 283\u2013308."},{"key":"R33","doi-asserted-by":"crossref","unstructured":"A. Okhotin, Strict language inequalities and their decision problems. InProc. of Mathematical Foundations of Computer Science, MFCS 2005, Gda\u0144sk, Poland, August 29\u2013September 2. In vol. 3618 ofLect. Notes Comput. Sci.(2005) 708\u2013719.","DOI":"10.1007\/11549345_61"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Okhotin A., Decision problems for language equations.J. Comput. Syst. Sci.76(2010) 251\u2013266.","DOI":"10.1016\/j.jcss.2009.08.002"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Okhotin A., Language equations with symmetric difference.Fundamenta Informaticae116(2012) 205\u2013222.","DOI":"10.3233\/FI-2012-679"},{"key":"R36","unstructured":"Okhotin A., Conjunctive and Boolean grammars: the true general case of the context-free grammars.Comput. Sci. Rev.9(2013) 27\u201359."},{"key":"R37","unstructured":"Okhotin A., Parsing by matrix multiplication generalized to Boolean grammars.Theoret. Comput. Sci.516(2014) 101\u2013120."},{"key":"R38","unstructured":"Okhotin A. and Reitwie\u00dfner C., Conjunctive grammars with restricted disjunction.Theoret. Comput. Sci.411(2010) 2559\u20132571."},{"key":"R39","unstructured":"Okhotin A. and Reitwie\u00dfner C., Parsing Boolean grammars over a one-letter alphabet using online convolution.Theoret. Comput. Sci.457(2012) 149\u2013157."},{"key":"R40","unstructured":"Okhotin A. and Rondogiannis P., On the expressive power of univariate equations over sets of natural numbers.Inform. Comput.212(2012) 1\u201314."},{"key":"R41","doi-asserted-by":"crossref","unstructured":"Okhotin A. and Yakimova O., Language equations with complementation: decision problems.Theoret. Comput. Sci.376(2007) 112\u2013126.","DOI":"10.1016\/j.tcs.2007.01.016"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Okhotin A. and Yakimova O., Language equations with complementation: expressive power.Theoret. Comput. Sci.416(2012) 71\u201386.","DOI":"10.1016\/j.tcs.2011.10.003"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"Post E.L., Introduction to a general theory of elementary propositions.Am. J. Math.43(1921) 163\u2013185.","DOI":"10.2307\/2370324"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"E.L. Post, The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press (1941).","DOI":"10.1515\/9781400882366"},{"key":"R45","unstructured":"Rabin M.O., Decidability of second-order theories and automata on infinite trees.Trans. Am. Math. Soc.141(1969) 1\u201335."},{"key":"R46","unstructured":"Rounds W.C., LFP: A logic for linguistic descriptions and an analysis of its complexity.Comput. Linguistics14(1988) 1\u20139."},{"key":"R47","unstructured":"S.V. Yablonski, G.P. Gavrilov and V.B. Kudryavtsev,Funktsii algebry logiki i klassy Posta(Functions of the logic algebra and the classes of Post). Nauka, Moscow (1966), in Russian, German translation:Boolesche Funktionen und Postsche Klassen. Akademie-Verlag, Berlin (1970)."},{"key":"R48","unstructured":"van Zijl L., On binary \u2295-NFAs and succinct descriptions of regular languages.Theoret. Comput. Sci.328(2004) 161\u2013170."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015006\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T15:39:27Z","timestamp":1653579567000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/2015006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7]]},"references-count":48,"journal-issue":{"issue":"3"},"alternative-id":["ita150025"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2015006","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7]]}}}