Computational Universality in One-variable Language Equations

• Autorzy: Okhotin A.
• Języki publikacji: EN

Abstrakty

EN

It has recently been shown that several computational models, such as trellis automata, recursive functions and Turing machines, admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is proved that the universality and the associated hardness of decision problems begins at one-variable equations. Additionally, it is shown that language equations with added quotient with regular languages can specify every set representable in first-order Peano arithmetic.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 563--578
• Opis fizyczny: bibliogr. 25 poz.

Twórcy

autor

Okhotin A.

• Department of Mathematics, University of Turku, FIN-20014 Turku, Finland,

Bibliografia

• [1] J. Autebert, J. Berstel, L. Boasson, "Context-free languages and pushdown automata", in: Rozenberg, Salomaa (Eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, Berlin, 1997, 111-174.
• [2] F. Baader, R. Küsters, "Solving linear equations over regular languages", Proceedings of the 15th International Workshop on Unification (UNIF 2001, June 18-19, 2001, Siena, Italy), 27-31.
• [3] B. S. Baker, R. V. Book, "Reversal-bounded multipushdown machines", Journal of Computer and System Sciences, 8 (1974), 315-332.
• [4] K. Culik II, J. Gruska, A. Salomaa, "Systolic trellis automata", I and II, International Journal of Computer Mathematics, 15 (1984), 195-212; 16 (1984), 3-22.
• [5] H. Fernau, "Nonterminal complexity of programmed grammars", Theoretical Computer Science, 296 (2003), 225-251.
• [6] S. Ginsburg, H. G. Rice, "Two families of languages related to ALGOL", Journal of the ACM, 9 (1962), 350-371.
• [7] J. Hartmanis, "Context-free languages and Turing machine computations", Proceedings of Symposia in Applied Mathematics, Vol. 19, AMS, Providence, RI, 1967, 42-51.
• [8] L. Kari, G. Thierrin, "Maximal and minimal solutions to language equations", Journal of Computer and System Sciences, 53:3 (1996), 487-496.
• [9] J. Karhumäki, I. Petre, "Two problems on commutation of languages", in: Gh. P˘aun, G. Rozenberg, A. Salomaa (Eds.), Current Trends in Theoretical Computer Science: The Challenge of the New Century, vol. 2, World Scientific, 2004, 477-494.
• [10] M. Kudlek, Yu. Rogozhin, "A Universal Turing Machine with 3 States and 9 Symbols", Developments in Language Theory (Proceedings of DLT 2001, Vienna, Austria, July 16-21, 2001), LNCS 2295, 311-318.
• [11] M. Kunc, "Regular solutions of language inequalities and well quasi-orders", Automata, Languages and Programming (Proceedings of ICALP 2004, Turku, Finland, July 12-16, 2004), LNCS 3142, 870-881.
• [12] M. Kunc, "The power of commuting with finite sets of words", STACS 2005 (Stuttgart, Germany, February 24-26, 2005), LNCS 3404, 569-580.
• [13] E. L. Leiss, "Unrestricted complementation in language equations over a one-letter alphabet", Theoretical Computer Science, 132 (1994), 71-93.
• [14] E. L. Leiss, Language equations, Springer-Verlag, New York, 1999.
• [15] A. Okhotin, "Conjunctive grammars", Journal of Automata, Languages and Combinatorics, 6:4 (2001), 519-535.
• [16] A. Okhotin, "Conjunctive grammars and systems of language equations", Programming and Computer Software, 28:5 (2002), 243-249.
• [17] A. Okhotin, "Decision problems for language equations with Boolean operations", Automata, Languages and Programming (Proceedings of ICALP 2003, Eindhoven, The Netherlands, June 30-July 4, 2003), LNCS 2719, 239-251; journal version submitted.
• [18] A. Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", Informatique Théorique et Applications, 38 (2004), 69-88.
• [19] A. Okhotin, "On the number of nonterminals in linear conjunctive grammars", Theoretical Computer Science, 320:2-3 (2004), 419-448.
• [20] A. Okhotin, "Boolean grammars", Information and Computation, 194:1 (2004), 19-48.
• [21] A. Okhotin, "On computational universality in language equations", Machines, Computations and Universality (Proceedings of MCU 2004, St.Petersburg, Russia, September 21-24, 2004), LNCS 3354, 292-303.
• [22] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967.
• [23] A. Salomaa, Theory of Automata, Pergamon Press, Oxford, 1969.
• [24] N. Yevtushenko, T. Villa, R. K. Brayton, A. Petrenko, A. L. Sangiovanni-Vincentelli, "Solution of parallel language equations for logic synthesis", Proceedings of ICCAD 2001 (San Jose, CA, USA, November 4-8, 2001), 103-110.
• [25] G.-Q. Zhang, "Domain mu-calculus", Informatique Théorique et Applications, 37 (2003), 337-364.