Language equations with complementation: expressive power. (English) Zbl 1279.68168
Summary: Consider a system of language equations of the form \(X_{i}=\varphi _{i} (X_{1},\ldots ,X_{n})\) (\(1\leqslant i \leqslant n\)), where every \(\varphi _{i}\) may contain the operations of concatenation and complementation. These systems have been studied in [the authors, Theor. Comput. Sci. 376, No. 1–2, 112–126 (2007; Zbl 1111.68062)]. This paper investigates the family of languages representable by unique solutions of such systems. A method for proving nonrepresentability of particular languages is developed. Several natural subfamilies of this family are compared to each other and to the main known families of formal languages. Their position in the hierarchy is established.
Citations:
Zbl 1111.68062Software:
ALGOL 60References:
| [1] | Baader, F.; Narendran, P., Unification of concept terms in description logic, Journal of Symbolic Computation, 31, 3, 277-305 (2001) · Zbl 0970.68166 |
| [2] | F. Baader, A. Okhotin, Complexity of language equations with one-sided concatenation and all Boolean operations, in: 20th International Workshop on Unification, UNIF 2006, Seattle, USA, August 11, 2006, pp. 59-73.; F. Baader, A. Okhotin, Complexity of language equations with one-sided concatenation and all Boolean operations, in: 20th International Workshop on Unification, UNIF 2006, Seattle, USA, August 11, 2006, pp. 59-73. |
| [3] | Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, Journal of the ACM, 9, 350-371 (1962) · Zbl 0196.01803 |
| [4] | Han, Y.-S.; Salomaa, A.; Salomaa, K.; Wood, D.; Yu, S., On the existence of prime decompositions, Theoretical Computer Science, 376, 1-2, 60-69 (2007) · Zbl 1111.68055 |
| [5] | Jeż, A., Conjunctive grammars can generate non-regular unary languages, International Journal of Foundations of Computer Science, 19, 3, 597-615 (2008) · Zbl 1155.68040 |
| [6] | Jeż, A.; Okhotin, A., Conjunctive grammars over a unary alphabet: undecidability and unbounded growth, Theory of Computing Systems, 46, 1, 27-58 (2010) · Zbl 1183.68327 |
| [7] | A. Jeż, A. Okhotin, On the computational completeness of equations over sets of natural numbers, in: 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, LNCS, vol. 5126, pp. 63-74.; A. Jeż, A. Okhotin, On the computational completeness of equations over sets of natural numbers, in: 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, LNCS, vol. 5126, pp. 63-74. · Zbl 1155.03309 |
| [8] | A. Jeż, A. Okhotin, Equations over sets of natural numbers with addition only, in: STACS 2009, Freiburg, Germany, 26-28 February, 2009, pp. 577-588.; A. Jeż, A. Okhotin, Equations over sets of natural numbers with addition only, in: STACS 2009, Freiburg, Germany, 26-28 February, 2009, pp. 577-588. · Zbl 1236.68171 |
| [9] | Kountouriotis, V.; Nomikos, Ch.; Rondogiannis, P., Well-founded semantics for Boolean grammars, Information and Computation, 207, 9, 945-967 (2009) · Zbl 1181.68162 |
| [10] | M. Kunc, On language inequalities \(X K \subseteq L X\); M. Kunc, On language inequalities \(X K \subseteq L X\) |
| [11] | Kunc, M., The power of commuting with finite sets of words, Theory of Computing Systems, 40, 4, 521-551 (2007) · Zbl 1121.68065 |
| [12] | Leiss, E. L., Unrestricted complementation in language equations over a one-letter alphabet, Theoretical Computer Science, 132, 71-93 (1994) · Zbl 0821.68076 |
| [13] | Mateescu, A.; Salomaa, A.; Yu, S., Factorizations of languages and commutativity conditions, Acta Cybernetica, 15, 3, 339-351 (2002) · Zbl 1065.68063 |
| [14] | Okhotin, A., Conjunctive grammars, Journal of Automata, Languages and Combinatorics, 6, 4, 519-535 (2001) · Zbl 1004.68082 |
| [15] | Okhotin, A., On the equivalence of linear conjunctive grammars to trellis automata, RAIRO Informatique Théorique et Applications, 38, 1, 69-88 (2004) · Zbl 1084.68079 |
| [16] | Okhotin, A., Boolean grammars, Information and Computation, 194, 1, 19-48 (2004) · Zbl 1073.68037 |
| [17] | Okhotin, A., The dual of concatenation, Theoretical Computer Science, 345, 2-3, 425-447 (2005) · Zbl 1079.68053 |
| [18] | A. Okhotin, Language equations with symmetric difference, in: Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, LNCS, vol. 3967, pp. 292-303.; A. Okhotin, Language equations with symmetric difference, in: Computer Science in Russia, CSR 2006, St. Petersburg, Russia, June 8-12, 2006, LNCS, vol. 3967, pp. 292-303. · Zbl 1185.68396 |
| [19] | Okhotin, A., Generalized LR parsing algorithm for Boolean grammars, International Journal of Foundations of Computer Science, 17, 3, 629-664 (2006) · Zbl 1098.68060 |
| [20] | Okhotin, A., Recursive descent parsing for Boolean grammars, Acta Informatica, 44, 3-4, 167-189 (2007) · Zbl 1119.68101 |
| [21] | Okhotin, A., Decision problems for language equations, Journal of Computer and System Sciences, 76, 3-4, 251-266 (2010) · Zbl 1201.68067 |
| [22] | Okhotin, A., Fast parsing for Boolean grammars: a generalization of Valiant’s algorithm, (Developments in Language Theory, DLT 2010, London, Ontario, Canada, August 17-20. Developments in Language Theory, DLT 2010, London, Ontario, Canada, August 17-20, LNCS, vol. 6224 (2010)), 340-351 · Zbl 1250.68145 |
| [23] | Okhotin, A.; Reitwießner, C., Conjunctive grammars with restricted disjunction, Theoretical Computer Science, 411, 26-28, 2559-2571 (2010) · Zbl 1203.68078 |
| [24] | Okhotin, A.; Yakimova, O., Language equations with complementation: decision problems, Theoretical Computer Science, 376, 1-2, 112-126 (2007) · Zbl 1111.68062 |
| [25] | Salomaa, A.; Yu, S., On the decomposition of finite languages, (Rozenberg, G.; Thomas, W., Developments in Language Theory. Developments in Language Theory, DLT 1999, Aachen, Germany, July 6-9, 1999 (2000), World Scientific), 22-31 · Zbl 1013.68099 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
