On language equations with concatenation and various sets of Boolean operations

Okhotin, Alexander

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 3, pp. 205-232.

Systems of equations of the form $X_i=\varphi {}_i(X_1,...,X_n)$, for 1 ⩽ i ⩽ n , in which the unknowns $X_i$ are formal languages, and the right-hand sides $\varphi {}_i$ may contain concatenation and union, are known for representing context-free grammars. If, instead of union only, another set of Boolean operations is used, the expressive power of such equations may change: for example, using both union and intersection leads to conjunctive grammars [A. Okhotin, J. Automata, Languages and Combinatorics 6 (2001) 519–535], whereas using all Boolean operations allows all recursive sets to be expressed by unique solutions [A. Okhotin, Decision problems for language equations with Boolean operations, Automata, Languages and Programming, ICALP 2003, Eindhoven, The Netherlands, 239–251]. This paper investigates the expressive power of such equations with any possible set of Boolean operations. It is determined that different sets of Boolean operations give rise to exactly seven families of formal languages: the recursive languages, the conjunctive languages, the context-free languages, a certain family incomparable with the context-free languages, as well as three subregular families.

J. Autebert, J. Berstel and L. Boasson, Context-free languages and pushdown automata. In vol. 1 of Handbook of Formal Languages, edited by Rozenberg, Salomaa. Springer–Verlag (1997) 111–174. | MR

F. Baader and R. Küsters, Unification in a description logic with transitive closure of roles, Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2001, Havana, Cuba. Vol. 2250 of Lect. Notes Comput. Sci. (2001) 217–232. | MR | Zbl

F. Baader and P. Narendran, Unification of concept terms in description logic. J. Symbolic Comput. 31 (2001) 277–305. | DOI | MR | Zbl

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érida, Venezuela. Vol. 7180 of Lect. Notes Comput. Sci. (2012) 107–121. | MR

F. Baader and A. Okhotin, On language equations with one-sided concatenation. Fundamenta Informaticae 126 (2013) 1–35. | DOI | MR | Zbl

S. Bala, 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–163. | DOI | MR | Zbl

J.A. Brzozowski and E.L. Leiss, On equations for regular languages, finite automata, and sequential networks. Theoret Comput. Sci. 10 (1980) 19–35. | DOI | MR | Zbl

M. Domaratzki and K. Salomaa, Decidability of trajectory-based equations. Theoret. Comput. Sci. 345 (2005) 304–330. | DOI | MR | Zbl

S. Ginsburg and H.G. Rice, Two families of languages related to ALGOL. J. ACM 9 (1962) 350–371. | DOI | MR | Zbl

A. Jeż, Conjunctive grammars can generate non-regular unary languages. Int. J. Found. Comput. Sci. 19 (2008) 597–615. | DOI | MR | Zbl

A. Jeż and A. Okhotin, Equations over sets of natural numbers with addition only. In Proc. of 26th Annual Symposium on Theoretical Aspects of Computer Science, Dagstuhl Seminar Proceedings 09001, STACS 2009, Freiburg, Germany, 26–28 February (2009) 577–588. | MR | Zbl

A. Jeż and A. Okhotin, Conjunctive grammars over a unary alphabet: undecidability and unbounded growth. Theory Comput. Syst. 46 (2010) 27–58. | DOI | MR | Zbl

A. Jeż and A. Okhotin, Least and greatest solutions of equations over sets of integers. In Proc. of Mathematical Foundations of Computer Science, MFCS 2010, Brno, Czech Republic. Vol. 6281 of Lect. Notes Comput. Sci. (2010) 441–452. | MR | Zbl

A. Jeż and A. Okhotin, Complexity of equations over sets of natural numbers. Theory Comput. Syst. 48 (2011) 319–342. | DOI | MR | Zbl

A. Jeż and A. Okhotin, One-nonterminal conjunctive grammars over a unary alphabet. Theory Comput. Syst. 49 (2011) 319–342. | DOI | MR | Zbl

A. Jeż and A. Okhotin, Representing hyper-arithmetical sets by equations over sets of integers. Theory Comput. Syst. 51 (2012) 196–228. | DOI | MR | Zbl

A. Jeż and A. Okhotin, Computational completeness of equations over sets of natural numbers. Inform. Comput. 237 (2014) 56–94. | DOI | MR | Zbl

L. Kari, On language equations with invertible operations. Theoret Comput. Sci. 132 (1994) 129–150. | DOI | MR | Zbl

V. Kountouriotis, Ch. Nomikos and P. Rondogiannis, Well-founded semantics for Boolean grammars. Inform. Comput. 207 (2009) 945–967. | DOI | MR | Zbl

M. Kunc, On language inequalities $XK\subseteq LX$. In Proc. of Developments in Language Theory, DLT 2005, Palermo, Italy. Vol. 3572 of Lect. Notes Comput. Sci. (2005) 327–337. | MR | Zbl

M. Kunc, The power of commuting with finite sets of words. Theory Comput. Syst. 40 (2007) 521–551. | DOI | MR | Zbl

D. Lau, Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory. Springer (2006). | MR | Zbl

T. Lehtinen, Equations $X+A=B$ and $(X+X)+C=(X-X)+D$ over sets of natural numbers. In Proc. of Mathematical Foundations of Computer Science, MFCS 2012, Bratislava, Slovakia, 27–31 August. In vol. 7464 of Lect. Notes Comput. Sci. (2012) 615–629. | MR

T. Lehtinen and A. Okhotin, On language equations $XXK=XXL$ and $XM=N$ over a unary alphabet. In Proc. of Developments in Language Theory, DLT 2010, London, Ontario, Canada. Vol. 6224 of Lect. Notes Comput. Sci. (2010) 291–302. | MR | Zbl

T. Lehtinen and A. Okhotin, On equations over sets of numbers and their limitations. Int. J. Found. Comput. Sci. 22 (2011) 377–393. | DOI | MR | Zbl

E.L. Leiss, Unrestricted complementation in language equations over a one-letter alphabet. Theoret. Comput. Sci. 132 (1994) 71–93. | DOI | MR | Zbl

W. Martens, M. Niewerth and T. Schwentick, Schema design for XML repositories: complexity and tractability, PODS 2010, Indianapolis, USA (2010) 239–250.

A. Okhotin, Conjunctive grammars. J. Automata, Languages and Combinatorics 6 (2001) 519–535. | MR | Zbl

A. Okhotin, Conjunctive grammars and systems of language equations. Program. Comput. Softw. 28 (2002) 243–249. | DOI | MR | Zbl

A. Okhotin, Decision problems for language equations with Boolean operations. In Proc. of Automata, Languages and Programming, ICALP 2003, Eindhoven, The Netherlands. Vol. 2719 of Lect. Notes Comput. Sci. (2003) 239–251. | MR | Zbl

A. Okhotin, Boolean grammars. Inform. Comput. 194 (2004) 19–48. | DOI | MR | Zbl

A. Okhotin, Unresolved systems of language equations: expressive power and decision problems. Theoret. Comput. Sci. 349 (2005) 283–308. | DOI | MR | Zbl

A. Okhotin, Strict language inequalities and their decision problems. In Proc. of Mathematical Foundations of Computer Science, MFCS 2005, Gdańsk, Poland, August 29–September 2. In vol. 3618 of Lect. Notes Comput. Sci. (2005) 708–719. | MR | Zbl

A. Okhotin, Decision problems for language equations. J. Comput. Syst. Sci. 76 (2010) 251–266. | DOI | MR | Zbl

A. Okhotin, Language equations with symmetric difference. Fundamenta Informaticae 116 (2012) 205–222. | DOI | MR | Zbl

A. Okhotin, Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9 (2013) 27–59. | DOI | Zbl

A. Okhotin, Parsing by matrix multiplication generalized to Boolean grammars. Theoret. Comput. Sci. 516 (2014) 101–120. | DOI | MR | Zbl

A. Okhotin and C. Reitwießner, Conjunctive grammars with restricted disjunction. Theoret. Comput. Sci. 411 (2010) 2559–2571. | DOI | MR | Zbl

A. Okhotin and C. Reitwießner, Parsing Boolean grammars over a one-letter alphabet using online convolution. Theoret. Comput. Sci. 457 (2012) 149–157. | DOI | MR | Zbl

A. Okhotin and P. Rondogiannis, On the expressive power of univariate equations over sets of natural numbers. Inform. Comput. 212 (2012) 1–14. | DOI | MR | Zbl

A. Okhotin and O. Yakimova, Language equations with complementation: decision problems. Theoret. Comput. Sci. 376 (2007) 112–126. | DOI | MR | Zbl

A. Okhotin and O. Yakimova, Language equations with complementation: expressive power. Theoret. Comput. Sci. 416 (2012) 71–86. | DOI | MR | Zbl

E.L. Post, Introduction to a general theory of elementary propositions. Am. J. Math. 43 (1921) 163–185. | DOI | JFM | MR

E.L. Post, The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press (1941). | MR | Zbl

M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Am. Math. Soc. 141 (1969) 1–35. | MR | Zbl

W.C. Rounds, LFP: A logic for linguistic descriptions and an analysis of its complexity. Comput. Linguistics 14 (1988) 1–9.

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). | MR

L. Van Zijl, On binary $\oplus$-NFAs and succinct descriptions of regular languages. Theoret. Comput. Sci. 328 (2004) 161–170. | MR | Zbl