×

zbMATH — the first resource for mathematics

Some undecidability results for non-monadic Church-Rosser Thue systems. (English) Zbl 0563.03019
A linear sentence on the alphabet A is a string of the form \(\forall u_ 1...\forall u_ m\exists v_ 1...\exists v_ nF\) or \(\exists v_ 1...\exists v_ n\forall u_ 1...\forall u_ mF\) where \(u_ i\in V_ u\), the set of universal variables, \(v_ i\in V_ E\), the set of existential variables and F has one of the forms \(x\sim y\) (x,y\(\in (A\cup V_ u)^*\cup (A\cup V_ E)^*)\), \(F_ 1\wedge F_ 2\), or \(F_ 1\vee F_ 2\) and no variable occurs twice in F. A Thue system on A defines an interpretation of the linear sentences on A by taking the congruence relation for \(\sim\). It is known that there is an algorithm which decides whether a linear sentence on A is true or not under the interpretation given by a monadic finite Thue system on A that is Church- Rosser. In the paper the case of non-monadic finite Thue systems that are Church-Rosser is considered. The main result claims that it is undecidable whether a linear sentence on A is true or not under the interpretation given by a non-monadic finite Thue system on A that is Church-Rosser. Some problems that are decidable for monadic Church-Rosser Thue systems but that are undecidable for non-monadic Church-Rosser Thue systems are presented.
Reviewer: D.Lucanu

MSC:
03D03 Thue and Post systems, etc.
03D35 Undecidability and degrees of sets of sentences
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bauer, G., Zur darstellung von monoiden durch konfluente regelsysteme, ()
[2] Book, R.V., Confluent and other types of thue systems, J. assoc. comput. Mach., 29, 171-182, (1982) · Zbl 0478.68032
[3] Book, R.V., When is a monoid a group? the church-rosser case is tractable, Theoret. comput. sci., 18, 325-331, (1982) · Zbl 0489.68021
[4] Book, R.V., Decidable sentences of church-rosser congruences, Theoret. comput. sci., 24, 301-312, (1983) · Zbl 0525.68015
[5] Book, R.V.; Jantzen, M.; Monien, B.; Wrathall, C., Results on thue systems and semigroups, () · Zbl 0482.03018
[6] Book, R.V.; Jantzen, M.; Wrathall, C., Monadic thue systems, Theoret. comput. sci., 19, 231-251, (1982) · Zbl 0488.03020
[7] Boone, W.W.; Boone, W.W.; Boone, W.W.; Boone, W.W.; Boone, W.W.; Boone, W.W., Certain simple unsolvable problems of group theory, VI, Nederl. akad. wetensch. proc. ser. A, Nederl. akad. wetensch. proc. ser. A, Nederl. akad. wetensch. proc. ser. A, Nederl. akad. wetensch. proc. ser. A, Nederl. akad. wetensch. proc. ser. A, Nederl. akad. wetensch. proc. ser. A, 60, 227-232, (1957) · Zbl 0173.01401
[8] Cobham, A., The intrinsic computational difficulty of functions, () · Zbl 0192.08702
[9] Grzegorczyk, A., Some classes of recursive functions, Rozprawy math., 4, 1-45, (1953)
[10] Herman, G.T., Strong computability and variants of the uniform halting problem, Zeitschr. f. math. logik u. grundl. d. math., 17, 115-131, (1971) · Zbl 0218.02033
[11] Hopcroft, J.E.; Ullman, J.D., Formal languages and their relation to automata, (1969), Addison-Wesley Reading, MA · Zbl 0196.01701
[12] Horster, P., Reduktionssysteme, formale sprachen und automatentheorie, () · Zbl 0563.03021
[13] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. assoc. comput. Mach., 27, 797-821, (1980) · Zbl 0458.68007
[14] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[15] Machtey, M., The honest subrecursive classes are a lattice, Inform. and control, 24, 247-263, (1974) · Zbl 0291.02026
[16] K. Madlener and F. Otto, Pseudo-natural algorithms for decision problems in combinatorial systems, submitted for publication.
[17] Meyer, A.R., Depth of nesting and the grzegorczyk hierarchy, Notices AMS, 12, 342, (1965)
[18] Nivat, M., On some families of languages related to the Dyck languages, 2nd ACM symp. on theory of computation, 221-225, (1970)
[19] Novikov, P.S., On the algorithmic unsolvability of the word problem in groups, Trudy mat. inst. Steklov, 44, (1955), Izdat. Akad. Nauk SSSR
[20] Ó’Dúnlaing, C.P., Finite and infinite regular thue systems, () · Zbl 0512.03018
[21] Ó’Dúnlaing, C.P., Infinite regular thue systems, Theoret. comput. sci., 25, 171-192, (1983) · Zbl 0512.03018
[22] Shepherdson, J.C., Machine configuration and word problems of given degrees of unsolvability, Zeitschr. f. math. logik u. grundl. d. math., 11, 149-175, (1965) · Zbl 0161.00803
[23] Weihrauch, K., Teilklassen primitiv-rekursiver wortfunktionen, Report no. 91, (1974), GMD Bonn · Zbl 0293.02026
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.