Decision problems for language equations. (English) Zbl 1201.68067
Summary: Equations with formal languages as unknowns using all Boolean operations and concatenation are studied. Their main properties, such as solution existence and uniqueness, are characterized by first-order formulae. It is shown that testing solution existence is \(\varPi _{1}\)-complete, while solution uniqueness and existence of a least and of a greatest solution are all \(\varPi _{2}\)-complete problems. The families of languages defined by components of unique, least and greatest solutions of such systems are shown to coincide with the classes of recursive, recursively enumerable and co-recursively enumerable sets, respectively.
MSC:
| 68Q45 | Formal languages and automata |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Software:
ALGOL 60References:
| [1] | Aiken, A.; Kozen, D.; Vardi, M. Y.; Wimmers, E. L., The complexity of set constraints, (Computer Science Logic. Computer Science Logic, CSL 1993, Swansea, United Kingdom, September 13-17, 1993. Computer Science Logic. Computer Science Logic, CSL 1993, Swansea, United Kingdom, September 13-17, 1993, Lecture Notes in Comput. Sci., vol. 832 (1994)), 1-17 · Zbl 0953.68557 |
| [2] | Autebert, J.; Berstel, J.; Boasson, L., Context-free languages and pushdown automata, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1 (1997), Springer), 111-174 |
| [3] | Baader, F.; Narendran, P., Unification of concept terms in description logic, J. Symbolic Comput., 31, 3, 277-305 (2001) · Zbl 0970.68166 |
| [4] | Baker, B. S.; Book, R. V., Reversal-bounded multipushdown machines, J. Comput. System Sci., 8, 315-332 (1974) · Zbl 0309.68043 |
| [5] | Brzozowski, J. A.; Leiss, E. L., On equations for regular languages, finite automata, and sequential networks, Theoret. Comput. Sci., 10, 19-35 (1980) · Zbl 0415.68023 |
| [6] | Charatonik, W., Set constraints in some equational theories, Inform. and Comput., 142, 1, 40-75 (1998) · Zbl 1034.68505 |
| [7] | Conway, J. H., Regular Algebra and Finite Machines (1971), Chapman and Hall · Zbl 0231.94041 |
| [8] | Daley, M.; Ibarra, O. H.; Kari, L., Closure and decidability properties of some language classes with respect to ciliate bio-operations, Theoret. Comput. Sci., 306, 19-38 (2003) · Zbl 1060.68060 |
| [9] | Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, J. ACM, 9, 350-371 (1962) · Zbl 0196.01803 |
| [10] | Hartmanis, J., Context-free languages and Turing machine computations, (Proc. Sympos. Appl. Math., vol. 19 (1967), AMS), 42-51 · Zbl 0189.29101 |
| [11] | Karhumäki, J.; Lisovik, L., The equivalence problem of finite substitutions on \(a b^\ast c\), with applications, Internat. J. Found. Comput. Sci., 14, 699-710 (2003) · Zbl 1101.68660 |
| [12] | Karhumäki, J.; Petre, I., Conway’s problem for three-word sets, Theoret. Comput. Sci., 289, 705-725 (2002) · Zbl 1061.68097 |
| [13] | Kari, L.; Konstantinidis, S., Language equations, maximality and error-detection, J. Comput. System Sci., 70, 157-178 (2005) · Zbl 1070.68070 |
| [14] | Kari, L.; Thierrin, G., Maximal and minimal solutions to language equations, J. Comput. System Sci., 53, 3, 487-496 (1996) · Zbl 0870.68094 |
| [15] | Kunc, M., What do we know about language equations?, (Developments in Language Theory. Developments in Language Theory, DLT 2007, Turku, Finland, July 3-6, 2007. Developments in Language Theory. Developments in Language Theory, DLT 2007, Turku, Finland, July 3-6, 2007, Lecture Notes in Comput. Sci., vol. 4588 (2007)), 23-27 |
| [16] | Leiss, E. L., Unrestricted complementation in language equations over a one-letter alphabet, Theoret. Comput. Sci., 132, 71-93 (1994) · Zbl 0821.68076 |
| [17] | Okhotin, A., Conjunctive grammars, J. Autom. Lang. Comb., 6, 4, 519-535 (2001) · Zbl 1004.68082 |
| [18] | Okhotin, A., Conjunctive grammars and systems of language equations, Program. Comput. Software, 28, 5, 243-249 (2002) · Zbl 1036.68063 |
| [19] | Okhotin, A., Boolean grammars, Inform. and Comput., 194, 1, 19-48 (2004) · Zbl 1073.68037 |
| [20] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill · Zbl 0183.01401 |
| [21] | Salomaa, A., Theory of Automata (1969), Pergamon Press · Zbl 0193.32901 |
| [22] | Yevtushenko, N.; Villa, T.; Brayton, R. K.; Petrenko, A.; Sangiovanni-Vincentelli, A. L., Solution of parallel language equations for logic synthesis, (International Conference on Computer-Aided Design. International Conference on Computer-Aided Design, ICCAD 2001, San Jose, CA, USA, November 4-8, 2001 (2001), ACM), 103-110 |
| [23] | Zhang, G.-Q., Domain mu-calculus, RAIRO Inf. Théor. Appl., 37, 337-364 (2003) · Zbl 1038.03038 |
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.
