Article

Free access

The regular problem and green equivalences for special monoids

Authors:

Jinzhao Wu,

Lian LiAuthors Info & Claims

ISSAC '93: Proceedings of the 1993 international symposium on Symbolic and algebraic computation

Pages 78 - 85

https://doi.org/10.1145/164081.164097

Published: 01 August 1993 Publication History

PDF eReader

References

[1]

R. V. Book, Decidable sentences of Church-Rosser congruences, Theoret. Comput. Sci. 24 (1983), 301-312.

Google Scholar

[2]

R. V. Book, Thue systems as rewriting sys-tems, J. Symbolic. Comput. 3 (1987), 39-68.

Digital Library

Google Scholar

[3]

R. V. Book, Conjluent and other types of Thue systems, J. Assoc. Comput.Mach.29 (1982), 171-182.

Digital Library

Google Scholar

[4]

R. V. Book, Thue systems and Church-Rosser property, replacement of systems, specification of formal languages, and presentations of monoids. in L. Cummings, ed. Combi-natorics on words: Progress and perspectives (Academic Press. Canada (1983), 1-38.

Google Scholar

[5]

A. H. Clifford, and G. B. Preston, The Alge-braic Theory of Semigroups, Math. Surveys of the American Math. Soc.7 F)rovidence, R. I. 1961.

Google Scholar

[6]

J. Hopcroft and J. Unman, Introduction to Automata Theory, Languages and Computa-tion, (Addition-Wesley, Reading, MA 1979).

Digital Library

Google Scholar

[7]

M. Jantzen, On a special monoid with a single defining relation, Theoret. Cornput. Sci. 16 (1981), 61-73.

Crossref

Google Scholar

[8]

D. Knuth, P. Bendix, Simple word prob-lems in universal algebra, in: J. Leeched.), Computational Problems in Abstract Alge-bra, Pergamon Press. 1970, 263-297.

Google Scholar

[9]

F. Otto, Deciding algebraic properties of finitely presented monoids, Lecture Notes in Computer Science (Spring: Berlin), 277 (1987), 218-263.

Google Scholar

Index Terms

The regular problem and green equivalences for special monoids
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Formal languages and automata theory
    1. Formalisms
      1. Rewrite systems
    2. Grammars and context-free languages

Recommendations

Recognizable languages in divisibility monoids

We define the class of divisibility monoids that arise as quotients of the free monoid Σ* modulo certain equations of the form ab = cd. These form a much larger class than free partially commutative monoids, and we show, under certain assumptions, that ...
Arrows, like Monads, are Monoids

Monads are by now well-established as programming construct in functional languages. Recently, the notion of ''Arrow'' was introduced by Hughes as an extension, not with one, but with two type parameters. At first, these Arrows may look somewhat ...
Divisibility Monoids: Presentation, Word Problem, and Rational Languages
FCT '01: Proceedings of the 13th International Symposium on Fundamentals of Computation Theory

We present three results on divisibility monoids. These divisibility monoids were introduced in [11] as an algebraic generalization of Mazurkiewicz trace monoids. (1) We give a decidable class of presentations that gives rise precisely to all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '93: Proceedings of the 1993 international symposium on Symbolic and algebraic computation

August 1993

321 pages

ISBN:0897916042

DOI:10.1145/164081

Editor:
Manuel Bronstein

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC93

Sponsor:

SIGSAM

ISSAC93: International Symposium on Symbolic and Algebraic

July 6 - 8, 1993

Kiev, Ukraine

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
118
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)13

Reflects downloads up to 03 Feb 2025

Other Metrics

View Author Metrics

Citations

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Index Terms

Recommendations

Recognizable languages in divisibility monoids

Arrows, like Monads, are Monoids

Divisibility Monoids: Presentation, Word Problem, and Rational Languages