Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Decidable sentences for context-free groups

  • Rewriting
  • Conference paper
  • First Online:
STACS 91 (STACS 1991)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 480))

Included in the following conference series:

  • 116 Accesses

Abstract

The linear sentences of Book [1983] are a class of logical formulae particularly well-suited for describing certain properties of Thue congruences. Here we show that the decidability of the set of valid linear sentences is an invariant property of finitely generated monoids. Further, we prove that for each finite monadic string-rewriting system R such that R presents a group, and R is confluent on

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

6. References

  1. J.M. Autebert, L. Boasson, G. Senizergues [1987]; Groups and NTS languages; J. Comput. System Sci. 35, 243–267.

    Article  Google Scholar 

  2. R.V. Book [1983]; Decidable sentences of Church-Rosser congruences; Theoretical Computer Science 24, 301–312.

    Article  Google Scholar 

  3. R.V. Book [1987]; Thue systems as rewriting systems; J. Symbolic Computation 3, 39–68.

    Google Scholar 

  4. R.H. Gilman [1979]; Presentations of groups and monoids; J. of Algebra 57, 544–554.

    Article  Google Scholar 

  5. J.E. Hopcroft, J.D. Ullman [1979]; Introduction to automata theory, languages, and computation [Addison-Wesley, Reading, MA].

    Google Scholar 

  6. K. Madlener, F. Otto [1988]; Communtativity in groups presented by finite Church-Rosser Thue systems; RAIRO Inf. Théorique et Appl. 22, 93–111.

    Google Scholar 

  7. K. Madlener, F. Otto [1989]; About the descriptive power of certain classes of finite string-rewriting systems; Theoretical Computer Science 67, 143–172.

    Article  Google Scholar 

  8. D.E. Muller, P.E. Schupp [1983]; Groups, the theory of ends, and context-free languages; J. Comput. System Sci. 26, 295–310.

    Article  Google Scholar 

  9. F. Otto [1984]; Some undecidability results for non-monadic Church-Rosser Thue systems; Theoretical Computer Science 33, 261–278.

    Article  Google Scholar 

  10. F. Otto, L. Zhang [1990]; Decision problems for finite special-string-rewriting systems that are confluent on some congruence class; Acta Informatica, to appear.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Informatik, Universität Kaiserslautern, Postfach 3049, D-6750, Kaiserslautern

    K. Madlener

  2. Fachbereich Mathematik, FG Informatik, Gesamthochschule Kassel, Postfach 101380, D-3500, Kassel

    F. Otto

Authors
  1. K. Madlener
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. Otto
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christian Choffrut Matthias Jantzen

Rights and permissions

Reprints and permissions

Copyright information

© 1991 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Madlener, K., Otto, F. (1991). Decidable sentences for context-free groups. In: Choffrut, C., Jantzen, M. (eds) STACS 91. STACS 1991. Lecture Notes in Computer Science, vol 480. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0020796

Download citation

  • DOI: https://doi.org/10.1007/BFb0020796

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-53709-0

  • Online ISBN: 978-3-540-47002-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation