×

zbMATH — the first resource for mathematics

\(X\)-automata on \(\omega\)-words. (English) Zbl 0777.68058
Five criteria for accepting infinite words were proposed by L. H. Landweber [Math. Systems Theory 3, 376-384 (1969; Zbl 0182.02402)]. The relative power of these five criteria have then been compared e.g. for finite-state automata, pushdown automata, Turing machines, and Petri nets. The results show that the acceptance types have the same relative power independently of the storage used by the automaton involved.
The paper investigates, using a general framework, the similarities between the results obtained for the various specific types of automata. The abstract model of storage used is called a storage type. It describes the storage configurations, together with the tests and transformations that can be applied to them. Automata equipped with a specific storage \(X\) are called \(X\) automata. Six families of \(\omega\)-languages that can be accepted by an \(X\) automaton using six different acceptance criteria on the sequence of states entered by the automaton during a computation are studied. The main tool is a characterisation of the \(\omega\)- languages accepted by \({\mathcal X}\) automata in terms of infinitary transductions applied to the \(\omega\)-languages accepted by finite-state automata. The inclusion results between the six families for \(X\)-automata are similar to those formed by the families for finite-state automata. It is also shown that the topological upper bounds as given by Landweber for deterministic finite-state automata can be generalized for \(X\) automata. This implies that for deterministic and real-time \(X\) automata the inclusions are strict.
Reviewer: M.Linna (Naasa)

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold, A., Topological characterizations of infinite behaviours of transition systems, (), 28-38
[2] Boasson, L.; Nivat, M., Adherences of languages, J. comput. system sci., 20, 285-309, (1980) · Zbl 0471.68052
[3] Büchi, J.R., On a decision method in restricted second order arithmetic, (), 1-11 · Zbl 0147.25103
[4] Carstensen, H., Fairness in deadlockfree Petri nets with the finite delay property, Proc. 5th European workshop on applications and theory of Petri nets, 234-253, (1984), Aarhus
[5] Carstensen, H., Infinite behaviour of deterministic Petri nets, (), 210-219
[6] Cohen, R.S.; Gold, A.Y., Theory of ω-languages. I: characterizations of ω-context-free languages, II: a study of various models of ω-type generation and recognition, J. comput. system sci., 15, 169-208, (1977) · Zbl 0363.68114
[7] Cohen, R.S.; Gold, A.Y., Ω-computations on deterministic pushdown machines, J. comput. system sci., 16, 275-300, (1978) · Zbl 0382.03025
[8] Cohen, R.S.; Gold, A.Y., Ω-computations on Turing machines, Theoret. comput. sci., 6, 1-23, (1978) · Zbl 0368.68057
[9] Eilenberg, S., Automata, languages and machines, (1974), Academic Press New York and London, Chapter XIV · Zbl 0317.94045
[10] Engelfriet, J.; Hoogeboom, H.J., Automata with storage on infinite words, (), 303-389
[11] Engelfriet, J.; Vogler, H., Look-ahead on pushdowns, Inform. and comput., 73, 245-279, (1987) · Zbl 0625.68063
[12] Ginsburg, S., Algebraic and automata-theoretic properties of formal languages, (1975), North-Holland/American Elsevier Amsterdam/New York · Zbl 0325.68002
[13] Ginsburg, S.; Greibach, S.A., Abstract families of languages, Studies in abstract families of languages, mem. amer. math. soc., 87, 1-32, (1969)
[14] Greibach, S.A., Remarks on blind and partially blind one-way multicounter machines, Theoret. comput. sci., 7, 311-324, (1978) · Zbl 0389.68030
[15] Hoogeboom, H.J.; Rozenberg, G., Infinitary languages - basic theory and applications to concurrent systems, (), 266-342 · Zbl 0607.68059
[16] Hopcroft, J.E.; Ullman, J.D., An approach to a unified theory of automata, The Bell system technical journal, XLVI, 1793-1829, (1967) · Zbl 0155.34303
[17] Hossley, R., Finite tree automata and ω-automata, MAC tech. report 102 MIT, (1972)
[18] Jantzen, M., On the hierarchy of Petri net languages, RAIRO inform. théor. appl., 13, 19-30, (1979) · Zbl 0404.68076
[19] Kobayashi, K.; Takahashi, M.; Yamasaki, H., Characterization of ω-regular languages by first order formulas, Theoret. comput. sci., 28, 315-327, (1984) · Zbl 0551.68069
[20] Landweber, L.H., Decision problems for ω-automata, Math. systems theory, 3, 376-384, (1969) · Zbl 0182.02402
[21] Latteux, M.; Timmerman, E., Two characterizations of rational adherences, Theoret. comput. sci., 46, 101-106, (1986) · Zbl 0618.68066
[22] Lindner, R.; Staiger, L., Algebraische codierungstheorie - theorie der sequentiellen codierungen, (1977), Akademie Berlin · Zbl 0363.94016
[23] Linna, M., On ω-sets associated with context-free languages, Inform. and control, 31, 272-293, (1976) · Zbl 0329.68066
[24] Linna, M., A decidability result for deterministic ω-context-free languages, Theoret. comput. sci., 4, 83-98, (1977) · Zbl 0357.68076
[25] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and control, 9, 521-530, (1966) · Zbl 0212.33902
[26] Muller, D.E., Infinite sequences and finite machines, AIEE proc. 4th ann. symp. switch. circuit theory and logical design, 3-16, (1963)
[27] Scott, D., Some definitional suggestions for automata theory, J. comput. system sci., 1, 187-212, (1967) · Zbl 0164.32103
[28] Staiger, L., Empty-storage-acceptance of ω-languages, (), 516-521
[29] Staiger, L., Finite-state ω-languages, J. comput. system sci., 27, 434-448, (1983) · Zbl 0541.68052
[30] Staiger, L., Projection lemmas for ω-languages, Theoret. comput. sci., 32, 331-337, (1984) · Zbl 0545.68074
[31] Staiger, L., Hierarchies of recursive ω-languages, Elektron. inform. verarb. kybern. EIK, 22, 219-241, (1986) · Zbl 0627.03024
[32] Staiger, L., Research in the theory of ω-languages, J. inform. process. cybern. EIK, 23, 415-439, (1987) · Zbl 0637.68095
[33] Staiger, L., Sequential mappings of ω-languages, RAIRO inform. théor. appl., 21, 147-173, (1987) · Zbl 0634.68070
[34] Staiger, L.; Wagner, K., Automatentheoretische und automatenfreie characterisierungen topologischer klassen regulaerer folgenmengen, Elektron. inform. verarb. kybern. EIK, 10, 379-392, (1974) · Zbl 0301.94069
[35] Staiger, L.; Wagner, K., Rekursive folgenmengen I, Z. math. logik grundlag. math., 24, 523-538, (1978) · Zbl 0421.03035
[36] Thomas, W., Automata on infinite objects, (), 133-191 · Zbl 0900.68316
[37] Thomas, W., Automata and quantifier hierarchies, ()
[38] Valk, R., Infinite behaviour of Petri nets, Theoret. comput. sci., 25, 311-341, (1983) · Zbl 0559.68057
[39] Wagner, K., On ω-regular sets, Inform. and control, 43, 123-177, (1979) · Zbl 0434.68061
[40] Wagner, K.; Staiger, L., Recursive ω-languages, (), 532-537 · Zbl 0367.02017
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.