ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The ω sequence problem for DOL systems is decidable
Full text pdf formatPdf (719 KB)
Source Journal of the ACM (JACM) archive
Volume 31 ,  Issue 2  (April 1984) table of contents
Pages: 282 - 298  
Year of Publication: 1984
ISSN:0004-5411
Authors
Karel Culik, II  University of Waterloo, Waterloo, Ontario, Canada
Tero Harju  University of Turku, Turku, Finland
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 0,   Downloads (12 Months): 18,   Citation Count: 0
Additional Information:

references   index terms   review   collaborative colleagues   peer to peer  

Tools and Actions: 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/62.2161
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
Richard Bellman, Introduction to matrix analysis (2nd ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
 
2
CULIK, K., II.On the decidability of the sequence equivalence problem for D0L systems. Theoret. Comput. Sci. 3 (1976), 75-84.
 
3
CULm, K., II. The ultimate equivalence problem for D0L systems. Acta Inf. 10 (1978), 79-84.
 
4
CULIK, K., II, AND FINS, I. The decidability of the equivalence problem for IDOL systems. Inf. Control 35 (1977), 20--39.
 
5
CULIK, K., II.Homomorphisms: Decidability, equality and test sets. In Formal Language Theory, Perspectives and Open Problems, R. Book, Ed. Academic Press, New York, 1980, pp. 167-194.
 
6
CULIK, K., 1I, AND S^LOM^A, A.On infinite words obtained by iterating morphisms. Theoret. Comput. Sci 19 (1982), 29-38.
 
7
EHRENFEUCHT, A., AND ROZENBERG, G. Every two equivalent D0L systems have a regular true envelop. Theoret. Comput. ScL 10 (1980), 45-52.
 
8
Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
 
9
GANTMACHER, F.R.The Theory of Matrices. Vol. II. Chelsea, New York, 1959.
 
10
LINNA, M.The decidability of the D0L prefix problem. Int. ~ Comput. Math. 6 (1977), 127-t42.
 
11
NIVAT, M.Infinite words, infinite trees, infinite computations. In Foundations of Computer Science, J.W. Barleer and J. vail Leeuwen, Eds. 1II.2, Mathematisch Centrum, Amsterdam, 1979, pp. 3-52.
 
12
Grzegorz Rozenberg , Arto Salomaa, Mathematical Theory of L Systems, Academic Press, Inc., Orlando, FL, 1980
 
13
SALOMAA, A.Morphisms of free monoids and language theory. In Formal Language Theory, Perspectives and Open Problems, R. Book, Ed. Academic Press, New York, 1980, pp. 141-166.
 
14
SALOMAA, A.Jewels in Formal Language Theory, Computer Science Press, Rockville, Md., 1981.
 
15
TtlUE, A.Uber unendliche Zcichenreichen. Norsk. Videnskapsselsk. Skr#er L Mat.-Nat. KI. Nr.7 (1906) 1-22.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Decision problems; Parallel rewriting systems (e.g., developmental systems, L-systems)


General Terms:
Theory, Verification


REVIEW

"Michael Hanns Heinrich Kunze : Reviewer"

This paper solves the decision problem in the title. Let &Sgr; be an alphabet and &sgr;1,&sgr;2:9I &sgr;*. The question is to decide whether iterated application of prefix-preserv  more...

Collaborative Colleagues:
Karel Culik, II: colleagues
Tero Harju: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player