Context-dependent nondeterminism for pushdown automata. (English) Zbl 1111.68060
Summary: Pushdown automata using a limited and unlimited amount of nondeterminism are investigated. Moreover, nondeterministic steps are allowed only within certain contexts, i.e., in configurations that meet particular conditions. The relationships of the accepted language families with closures of the deterministic context-free languages (DCFL) under regular operations are studied. For example, automata with unbounded nondeterminism that have to empty their pushdown store up to the initial symbol in order to make a guess are characterized by the regular closure of DCFL. Automata that additionally have to reenter the initial state are (almost) characterized by the Kleene star closure of the union closure of the prefix-free deterministic context-free languages. Pushdown automata with bounded nondeterminism are characterized by the union closure of DCFL in any of the considered contexts. Proper inclusions between all language classes discussed are shown. Finally, closure properties of these families under AFL operations are investigated.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
deterministic pushdown automata; computational capacity; time-efficient recognizers; closures of languages; context-free languagesReferences:
| [1] | Bertsch, E.; Nederhof, M. J., Regular closure of deterministic languages, SIAM J. Comput., 29, 81-102 (1999) · Zbl 0937.68073 |
| [2] | Cai, L.; Chen, J., On the amount of nondeterminism and the power of verifying, SIAM J. Comput., 26, 733-750 (1997) · Zbl 0870.68062 |
| [3] | Fischer, P. C.; Kintala, C. M.R., Real-time computations with restricted nondeterminism, Math. Syst. Theory, 12, 219-231 (1979) · Zbl 0409.68027 |
| [4] | Goldsmith, J.; Levy, M. A.; Mundhenk, M., Limited nondeterminism, SIGACT News, 27, 20-29 (1996) |
| [5] | Goldstine, J.; Kintala, C. M.; Wotschke, D., On measuring nondeterminism in regular languages, Inform. Comput., 86, 179-194 (1990) · Zbl 0698.68068 |
| [6] | Goldstine, J.; Leung, H.; Wotschke, D., Measuring nondeterminism in pushdown automata, J. Comput. System Sci., 71, 440-466 (2005) · Zbl 1101.68653 |
| [7] | Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058 |
| [8] | Herzog, C., Pushdown automata with bounded nondeterminism and bounded ambiguity, Theoret. Comput. Sci., 181, 141-157 (1997) · Zbl 0901.68132 |
| [9] | C. Herzog, Nondeterminism in context-free languages. Ph.D. Thesis, University of Frankfurt, Germany, 1999 (in German); C. Herzog, Nondeterminism in context-free languages. Ph.D. Thesis, University of Frankfurt, Germany, 1999 (in German) |
| [10] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Language, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [11] | Hromkovič, J.; Seibert, S.; Karhumäki, J.; Klauck, H.; Schnitger, G., Communication complexity method for measuring nondeterminism in finite automata, Inform. Comput., 172, 202-217 (2002) · Zbl 1009.68067 |
| [12] | C.M. Kintala, Computations with a restricted number of nondeterministic steps. Ph.D. Thesis, Pennsylvania State University, 1977; C.M. Kintala, Computations with a restricted number of nondeterministic steps. Ph.D. Thesis, Pennsylvania State University, 1977 |
| [13] | Kintala, C. M.; Wotschke, D., Amounts of nondeterminism in finite automata, Acta Inform., 13, 199-204 (1980) · Zbl 0423.68016 |
| [14] | Kutrib, M., Refining nondeterminism below linear time, J. Autom. Lang. Comb., 7, 533-547 (2002) · Zbl 1095.68594 |
| [15] | M. Kutrib, A. Malcher, Finite turns and the regular closure of linear context-free languages (2006) (submitted for publication); M. Kutrib, A. Malcher, Finite turns and the regular closure of linear context-free languages (2006) (submitted for publication) · Zbl 1123.68062 |
| [16] | Salomaa, K.; Yu, S., Limited nondeterminism for pushdown automata, Bull. EATCS, 50, 186-193 (1993) · Zbl 1023.68621 |
| [17] | Salomaa, K.; Yu, S., Measures of nondeterminism for pushdown automata, J. Comput. System Sci., 49, 362-374 (1994) · Zbl 0822.68070 |
| [18] | Vermeir, D.; Savitch, W., On the amount of nondeterminism in pushdown automata, Fund. Inform., 4, 401-418 (1981) · Zbl 0528.68034 |
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.
