×

New techniques for proving the decidability of equivalence problem. (English) Zbl 0699.68092

See the review in Zbl 0662.68079.

MSC:

68Q45 Formal languages and automata
68Q42 Grammars and rewriting systems
03B25 Decidability of theories and sets of sentences

Software:

ALGOL 60
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert, J.; Culik, K.; Karhumäki, J., Test sets for context-free languages and algebraic systems of equations, Inform. and Control, 52, 172-186 (1982) · Zbl 0522.68064
[2] Albert, M. H.; Lawrence, J., Test sets for finite substitutions, Theoret. Comput. Sci., 43, 117-122 (1986) · Zbl 0592.68066
[3] Albert, M. H.; Lawrence, J., A proof of Ehrenfeucht Conjecture, Theoret. Comput. Sci., 41, 121-123 (1985) · Zbl 0602.68066
[4] Bar-Hillel, Y.; Perles, M.; Shamir, E., On formal properties of simple phrase structure grammars, Z. Phonetik. Z. Phonetik, Sprachwiss. Kommunikationforsch., 14, 143-172 (1961) · Zbl 0106.34501
[5] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[6] Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. System Sci., 7, 218-236 (1973) · Zbl 0271.94039
[7] Blattner, M.; Head, T., Single-valued \(a\)-transducers, J. Comput. System Sci., 15, 310-327 (1977) · Zbl 0367.94071
[8] Blattner, M.; Head, T., The decidability of equivalence for deterministic finite transducers, J. Comput. System Sci., 19, 45-49 (1979) · Zbl 0416.68073
[9] Culik, K., Some decidability results about regular and pushdown translations, Inform. Process. Lett., 8, 5-8 (1979) · Zbl 0397.68083
[10] Culik, K.; Fris, I., The decidability of the equivalence problem for DOL systems, Inform. and Control, 35, 20-39 (1977) · Zbl 0365.68074
[11] Culik, K.; Karhumäki, J., Systems of equations over a free monoid and Ehrenfeucht Conjecture, Discrete Math., 43, 139-153 (1983) · Zbl 0528.68057
[12] Culik, K.; Karhumäki, J., A new proof for the DOL sequence equivalence problem and its implications, (Rozenberg, G.; Salomaa, A., The Book of L (1986), Springer: Springer Berlin), 63-74
[13] Culik, K.; Karhumäki, J., The decidability of the DTOL sequence equivalence problem and related decision problems, (Laakso, H.; Salomaa, A., The Very Knowledge of Coding (1987), University Press, Univ. of Turku), 43-54
[14] Culik, K.; Karhumäki, J., The equivalence problem for single-valued two-way transducers (on NPDTOL languages) is decidable, SIAM J. Comput., 16, 221-230 (1987) · Zbl 0632.68077
[15] Culik, K.; Karhumäki, J., The equivalence problem for finite-valued transducers (on HDTOL languages) is decidable, Theoret. Comput. Sci., 47, 71-84 (1986) · Zbl 0621.68049
[16] Culik, K.; Karhumäki, J., Synchronizable pushdown automata and the decidability of their equivalence, Acta Inform., 23, 598-605 (1986) · Zbl 0617.68075
[17] K. Culik II and J. Karhumäki, Loops in automata and HDTOL relations, RAIRO Inform. Théor.; K. Culik II and J. Karhumäki, Loops in automata and HDTOL relations, RAIRO Inform. Théor. · Zbl 0701.68079
[18] K. Culik II and J. Karhumäki, HDTCL matching of computations of multitape automata, Acta Inform.; K. Culik II and J. Karhumäki, HDTCL matching of computations of multitape automata, Acta Inform.
[19] Culik, K.; Salomaa, A., On the decidability of morphic equivalence for languages, J. Comput. System Sci., 17, 163-175 (1978) · Zbl 0389.68042
[20] Culik, K.; Salomaa, A., Test sets and checking words for homomorphism equivalence, J. Comput. System. Sci., 20, 379-395 (1980) · Zbl 0451.68046
[21] Friedman, E. P., The inclusion problem for simple languages, Theoret. Comput. Sci., 1, 297-316 (1976) · Zbl 0349.68032
[22] Friedman, E. P., The equivalence problem for deterministic context-free languages and monadic recursion schemes, J. Comput. System. Sci., 14, 344-359 (1977) · Zbl 0358.68109
[23] Fischer, P. C.; Rosenberg, A. L., Multi-tape one-way nonwriting automata, J. Comput. System. Sci., 2, 88-101 (1968) · Zbl 0159.01504
[24] Ginsburg, S.; Rose, G. F., Some recursively unsolvable problems in ALGOL-like languages, J. ACM, 10, 29-47 (1963) · Zbl 0134.01302
[25] Griffiths, T., The unsolvability of the equivalence problem for ϵ-free nondeterministic generalized sequential machines, J. ACM, 15, 409-413 (1968) · Zbl 0162.02302
[26] V.S. Guba, Personal communication, 1985.; V.S. Guba, Personal communication, 1985.
[27] Gurari, E., The equivalence problem for deterministic two-way transducers is decidable, SIAM J. Comput., 11, 448-452 (1982) · Zbl 0486.68037
[28] Harrison, M. A., Introduction to Formal Language Theory (1979), Addison-Wesley: Addison-Wesley Reading, MA
[29] Harrison, M. A.; Havel, I. M.; Yehudai, A., On equivalence of grammars through transformation trees, Theoret. Comput. Sci., 9, 173-205 (1979) · Zbl 0409.68041
[30] Ibarra, O., The unsolvability of the equivalence problem for ϵ-free NGSM’s with unary input (output) alphabet and applications, SIAM J. Comput., 4, 524-532 (1978) · Zbl 0386.68054
[31] Ibarra, O.; Rossier, L., On the decidability of equivalence for deterministic pushdown transducers, Inform. Process. Lett., 13, 89-93 (1981) · Zbl 0473.68077
[32] Jones, N.; Laaser, W., Complete problems for deterministic polynomial time, Theoret. Comput. Sci., 3, 105-117 (1977) · Zbl 0352.68068
[33] Karhumäki, J., The Ehrenfeucht Conjecture: A compactness claim for finitely generated free monoids, Theoret. Comput. Sci., 29, 285-308 (1984) · Zbl 0546.68060
[34] Karhumäki, J., The Ehrenfeucht conjecture for transducers, Elektron. Informationsverarb. Kybernet., 23, 389-401 (1987) · Zbl 0641.68108
[35] Karhumäki, J., On recent trends in formal language theory, (Proc. 14th ICALP. Proc. 14th ICALP, Lecture Notes in Computer Science, 267 (1987), Springer: Springer Berlin), 136-162
[36] Karhumäki, J., The impact of the DOL problem, Bull. EATCS, 34, 41-46 (1988) · Zbl 0666.68056
[37] Karhumäki, J.; Kleijn, H. C.M., On the equivalence of compositions of morphisms and inverse morphisms on regular languages, RAIRO Inform. Théor., 19, 203-211 (1985) · Zbl 0601.68049
[38] Kinber, E. B., The inclusion problem for some classes of deterministic multitape automata, Theoret. Comput. Sci., 26, 1-24 (1983) · Zbl 0523.68047
[39] Knuth, D. E., On the translation of languages from left to right, Inform. and Control, 8, 607-639 (1965) · Zbl 0231.68027
[40] Korenjak, A. J.; Hopcroft, J. E., Simple deterministic languages, Proc. IEEE 7th Ann. Symp. on Switching and Automata Theory, 36-46 (1966), Berkeley, CA · Zbl 0313.68061
[41] Lewis, H. R., A new decidable problem, with applications, Proc. 18th FOCS, 62-73 (1979)
[42] de Luca, A.; Pestivo, A., On a generalization of a conjecture of Ehrenfeucht, Bull. EATCS, 30, 84-90 (1986) · Zbl 1023.68608
[43] Makanin, G. S., The problem of solvability of equations in a free semigroup, Mat. Sb. (N.S.). Mat. Sb. (N.S.), Math. USSR-Sb., 32, 129-198 (1977), English transl. · Zbl 0396.20037
[44] Maon, Y., Decision problems concerning equivalence of transductions on languages, (Ph.D. Thesis (1985), Tel Aviv University)
[45] McNaughton, R., A proof of the Ehrenfeucht conjecture, Informal memorandum (1985)
[46] Moore, E. F., Gedanken-experiments on sequential machines, (Automata Studies (1956), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ), 129-153
[47] Oyamaguchi, M., The equivalence problem for real-time DPDAs, J. ACM, 34, 731-760 (1987) · Zbl 0637.68094
[48] Oyamaguchi, M.; Honda, N., The decidability of equivalence for deterministic stateless pushdown automata, Inform. and Control, 38, 367-376 (1978) · Zbl 0393.68078
[49] Oyamaguchi, M.; Honda, N.; Inagaki, Y., The equivalence problem for real-time strict deterministic languages, Inform. and Control, 45, 90-115 (1980) · Zbl 0444.68038
[50] Perrin, D., On the solution of Ehrenfeucht conjecture, Bull. EATCS, 27, 68-70 (1985)
[51] Poulsen, E. T., The Ehrenfeucht conjecture: An algebra-framework for its proof, Theoret. Comput. Sci., 44, 333-339 (1986) · Zbl 0599.20092
[52] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Develop., 3, 114-125 (1959) · Zbl 0158.25404
[53] Romanovsky, V. J., The equivalence problem for real-time deterministic pushdown automata, Kybernetika, 2, 13-23 (1986), (in Russian)
[54] Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press New York · Zbl 0365.68072
[55] Rosenkrants, D. J.; Stearns, D. J., Properties of deterministic top-down grammars, Inform. and Control, 17, 226-256 (1970) · Zbl 0209.02703
[56] Salomaa, A., The Ehrenfeucht conjecture: A proof for language theorists, Bull. EATCS, 27, 71-82 (1985)
[57] Salomaa, A.; Soittola, M., Automata-theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[58] Schützenberger, M. P., Sur les relations rationnelles, (Lecture Notes in Computer Science, 33 (1975), Springer: Springer Berlin), 209-312 · Zbl 0334.68045
[59] Stallings, J. R., Finiteness properties of matrix representations, Ann. Math., 124, 337-346 (1986) · Zbl 0604.20027
[60] Tomita, E., A direct branching algorithm for checking equivalence of strict deterministic vs. LL \((k)\) grammars, Theoret. Comput. Sci., 23, 129-154 (1983) · Zbl 0509.68072
[61] Valiant, L. G., The equivalence problem for deterministic finite-turn pushdown automata, Inform. and Control, 25, 123-133 (1974) · Zbl 0285.68025
[62] Valiant, L. G.; Paterson, M. S., Deterministic one-counter automata, J. Comput. System. Sci., 10, 340-350 (1975) · Zbl 0307.68038
[63] Weber, A.; Seidel, H., On the degree of ambiguity of finite automata, (Proc. MFCS 1986. Proc. MFCS 1986, Lecture Notes in Computer Science, 233 (1986), Springer: Springer Berlin), 620-629
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.