Decidability of the multiplicity equivalence of multitape finite automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decidability of the multiplicity equivalence of multitape finite automata

Full text

Pdf (352 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 477 - 481

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

T. Harju	Dept. of Mathematics, University of Turku, SF-20500 Turku, Finland
J. Karhumäki	Dept. of Mathematics, University of Turku, SF-20500 Turku, Finland

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 16, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100281 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	[Be] Berstel, J., Transductions and Context-Free Languages , B.G. Teubner, Stuttgart, 1979.
	2	Jean Berstel, Jr. , Christophe Reutenauer, Rational series and their languages, Springer-Verlag New York, Inc., New York, NY, 1988
	3	[Bi] Bird, M., The equivalence problem for deterministic two-tape automata, J. Comput. System Sci. 7 (1973) 218-236.
	4	[C] Cohn, P.M., Free Rings and their Realtions, Academic Press, New York London, 1985 (2nd ed).
	5	K. Culik, II , J. Karhumäki, HDTOL matching of computations of multitape automata, Acta Informatica, v.27 n.2, p.179-191, Nov. 1989 [doi>10.1007/BF00265153]
	6	Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
	7	[F] Fuchs, L., Partially Ordered Algebraic Systems, Pergamon Press, Oxford, 1963.
	8	T. V. Griffiths, The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines, Journal of the ACM (JACM), v.15 n.3, p.409-413, July 1968 [doi>10.1145/321466.321473]
	9	[J] Jacobson, N., Lectures in Abstract Algebra, Vol. II, Van Nostrand, New York, 1953.
	10	J. Karhumäki, On recent trends in formal language theory, 14th International Colloquium on Automata, languages and programming, p.136-162, July 1987, Karlsruhe, Germany
	11	[Ki] Kinber, E., The inclusion problem for some classes of deterministic multitape automata, Theoret. Comput. Sci. 26 (1983) 1-24.
	12	[L] Lewis, H.R., A new decidability problem with applications, Proceedings of 18th FOCS Conference (1979) 62-73.
	13	[N] Neumann, B.H., On ordered division rings, Trans. Amer. Math. Soc., 66 (1949) 202-252.
	14	[P] Passman D.S., The Algebraic Structure of Group Rings, John Wiley & Sons, New York, 1977.
	15	[RS] Rabin, M. and Scott, D., Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959) 114-125.
	16	Arto Salomaa , M. Soittola, Automata: Theoretic Aspects of Formal Power Series, Springer-Verlag New York, Inc., Secaucus, NJ, 1978
	17	[V] Valiant, L.G., The equivalence problem for deterministic finite-turn pushdown automata, Inform. Control, 25 (1974) 123-133.

CITED BY 3

	N. Kuhn , K. Madlener , F. Otto, A test for λ-confluence for certain prefix rewriting systems with applications to the generalized word problem, Proceedings of the international symposium on Symbolic and algebraic computation, p.8-15, August 20-24, 1990, Tokyo, Japan
	Daowen Qiu , Sheng Yu, Hierarchy and equivalence of multi-letter quantum finite automata, Theoretical Computer Science, v.410 n.30-32, p.3006-3017, August, 2009
	Christian Choffrut , Serge Grigorieff, The "equal last letter" predicate for words on infinite alphabets and classes of multitape automata, Theoretical Computer Science, v.410 n.30-32, p.2870-2884, August, 2009