Friedrich Otto

Theor. Comput. Sci., 2003

McNaughton families of languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Restarting Automata and Their Relations to the Chomsky Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 7th International Conference, 2003

Restarting Automata and Variants of j-Monotonicity.

[BibT_eX]

Martin Plátek

Frantisek Mráz

Proceedings of the 5th International Workshop on Descriptional Complexity of Formal Systems - DCFS 2003, Budapest, Hungary, July 12, 2003

Church-Rosser Languages and Their Relationship to Other Language Classes.

[BibT_eX]

Proceedings of the Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, 2003

2002

A Completion Procedure for Finitely Presented Groups That Is Based on Word Cycles.

[BibT_eX]

[DOI]

J. Autom. Reason., 2002

Some Exact Sequences for The Homotopy (Bi-)Module af A Monoid.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2002

2001

Confluent Monadic String-Rewriting Systems and Automatic Structures.

[BibT_eX]

[DOI]

Nikola Ruskuc

J. Autom. Lang. Comb., 2001

On Homotopical and Homological Finiteness Conditions for Finitely Presented Monoids.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2001

On the Relationship between the McNaughton Families of Languages and the Chomsky Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

On the Power of RRWW-Automata.

[BibT_eX]

Proceedings of the Words, Semigroups, and Transductions, 2001

2000

Repetitiveness of languages generated by morphisms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

On Dehn Functions of Finitely Presented Bi-Automatic Monoids.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2000

The Property Fdt is Undecidable for Finitely Presented Monoids that Have Polynomial-Time Decidable Word Problems.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2000

Undecidability Results for Monoids with Linear-Time Decidable Word Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

Further Results on Restarting Automata.

[BibT_eX]

Proceedings of the International Colloquium on Words, 2000

Confluent Internal Contextual Languages.

[BibT_eX]

Proceedings of the Recent Topics in Mathematical and Computational Linguistics, 2000

1999

On the Connections between Rewriting and Formal Language Theory.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 10th International Conference, 1999

Restarting automata, Church-Rosser languages, and representations of r.e. languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 1999

On S-Regular Prefix-Rewriting Systems and Automatic Structures.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

Equational Unification, Word Unification, and 2nd-Order Equational Unification.

[BibT_eX]

[DOI]

Daniel J. Dougherty

Theor. Comput. Sci., 1998

Some Undecidability Results Concerning the Property of Preserving Regularity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Infinite Convergent String-Rewriting Systems and Cross-Sections for Finitely Presented Monoids.

[BibT_eX]

[DOI]

J. Symb. Comput., 1998

Growing Context-Sensitive Languages and Church-Rosser Languages.

[BibT_eX]

[DOI]

Gerhard Buntrock

Inf. Comput., 1998

Automatic Monoids Versus Monoids with Finite Convergent Presentations.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 9th International Conference, 1998

1997

Single Versus Simultaneous Equational Unification and Equational Unification for Variable-Permuting Theories.

[BibT_eX]

[DOI]

J. Autom. Reason., 1997

Some Undecidability Results for Finitely Generated Thue Congruences on aTwo-Letter Alphabet.

[BibT_eX]

[DOI]

Fundam. Informaticae, 1997

Cross-Sections for Finitely Presented Monoids with Decidable Word Problems.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 8th International Conference, 1997

On the Property of Preserving Regularity for String-Rewriting Systems.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 8th International Conference, 1997

Repetitiveness of D0L-Languages Is Decidable in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

FDT is Undecidable for Finitely Presented Monoids with Solvable Word Problems.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

A Complete Characterization of Repetitive Morphisms over the Two-Letter Alphabet.

[BibT_eX]

[DOI]

Patrice Séébold

Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

Properties of Monoids That Are Presented by Finite Convergent String-Rewriting Systems - A Survey.

[BibT_eX]

Proceedings of the Advances in Algorithms, Languages, and Complexity, 1997

1996

For Groups the Property of Having Finite Derivation Type is Equivalent to the Homological Finiteness Condition FP_3.

[BibT_eX]

[DOI]

J. Symb. Comput., 1996

1995

On Confluence Versus Strong Confluence for One-Rule Trace-Rewriting Systems.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1995

Solvability of Word Equations Modulo Finite Special and Confluent String-Rewriting Systems is Undecidable in General.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

Some Independent Results for Equational Unification.

[BibT_eX]

[DOI]

Daniel J. Dougherty

Proceedings of the Rewriting Techniques and Applications, 6th International Conference, 1995

1994

A Finiteness Condition for Rewriting Systems.

[BibT_eX]

[DOI]

Craig C. Squier

Theor. Comput. Sci., 1994

Codes Modulo Finite Monadic String-Rewriting Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Finite Derivation Type Implies the Homological Finiteness Condition FP_3.

[BibT_eX]

[DOI]

J. Symb. Comput., 1994

Computing Presentations for Subgroups of Polycyclic Groups and of Context-Free Groups.

[BibT_eX]

[DOI]

Norbert Kuhn

Appl. Algebra Eng. Commun. Comput., 1994

Constructing Canonical Presentations for Subgroups of Context-Free Groups in Polynomial Time (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1994

1993

On Weakly Confluent Monadic String-Rewriting Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

Separating the Intrinsic Complexity and the Derivational complexity of the Word Problem for Finitely Presented Groups.

[BibT_eX]

[DOI]

Daniel E. Cohen

Math. Log. Q., 1993

On the Problem of Generating Small Convergent Systems.

[BibT_eX]

[DOI]

J. Symb. Comput., 1993

String-Rewriting Systems.

[BibT_eX]

[DOI]

Texts and Monographs in Computer Science, Springer, ISBN: 978-1-4613-9771-7, 1993

1992

The Problem of Deciding Confluence on a Given Congruence Class is Tractable for Finite Special String-Rewriting Systems.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1992

One-Rule Trace-Rewriting Systems and Confluence.

[BibT_eX]

[DOI]

Celia Wrathall

Volker Diekert

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Computing Presentations for Subgroups of Context-Free Groups.

[BibT_eX]

[DOI]

Norbert Kuhn

Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, 1992

Generating Small Convergent Systems Can Be Extremely Hard.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

1991

When is an Extension of a Specification Consistent? Decidable and Undecidable Cases.

[BibT_eX]

[DOI]

J. Symb. Comput., 1991

Overlaps in Free Partially Commutative Monoids.

[BibT_eX]

[DOI]

Celia Wrathall

J. Comput. Syst. Sci., 1991

It is undecidable whether a finite special string-rewriting system presents a group.

[BibT_eX]

[DOI]

Colm Ó'Dúnlaing

Discret. Math., 1991

Decision Problems for Finite Special String-Rewriting Systems that are Confluent on Some Congruence Class.

[BibT_eX]

[DOI]

Louxin Zhang

Acta Informatica, 1991

Completing a Finite Special String-Rewriting System on the Congruence Class of the Empty Word.

[BibT_eX]

[DOI]

Appl. Algebra Eng. Commun. Comput., 1991

Decidable Sentences for Context-Free Groups.

[BibT_eX]

[DOI]

Proceedings of the STACS 91, 1991

A Specialized Completion Procedure for Monadic String-Rewriting Systems Presenting Groups.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Some Undecidability Results for Weakly Confluent Monadic String-Rewriting Systems.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1991

1990

On Ground-Confluence of Term Rewriting Systems

[BibT_eX]

[DOI]

Deepak Kapur

Inf. Comput., May, 1990

A Test for lambda-Confluence for Certain Prefix Rewriting Systems with Applications to the Generalized Word Problem.

[BibT_eX]

[DOI]

Norbert Kuhn

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1990

Some Results on Equational Unification.

[BibT_eX]

[DOI]

Proceedings of the 10th International Conference on Automated Deduction, 1990

1989

On Deciding Confluence of Finite String-Rewriting Systems Modulo Partial Commutativity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Some Polynomial-Time Algorithms for Finite Monadic Church-Rosser Thue Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

About the Descriptive Power of Certain Classes of Finite String-Rewriting Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

Restrictions of Congruence Generated by Finite Canonical String-Rewriting Systems.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 3rd International Conference, 1989

1988

Pseudo-Natural Algorithms for Finitely Generated Presentations of Monoids and Groups.

[BibT_eX]

[DOI]

J. Symb. Comput., 1988

Church-Rosser Thue systems and formal languages.

[BibT_eX]

[DOI]

Robert McNaughton

J. ACM, 1988

Commutativity in Groups Presented By Finite Church-Rosser Thue Systems.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1988

Preperfectness is Undecidable for Thue Systems Containing Only Length-Reducing Rules and a Single Commutation Rule.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1988

An example of a one-relator group that is not a one-relation monoid.

[BibT_eX]

[DOI]

Discret. Math., 1988

Elements of Finite Order for Finite Weight-Reducing and Confluent Thue Systems.

[BibT_eX]

[DOI]

Acta Informatica, 1988

1987

Finite Canonical Rewriting Systems for Congruences Generated by Concurrency Relations.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1987

On Deciding the Confluence of a Finite String-Rewriting System on a Given Congruence Class.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1987

Using String-Rewriting for Solving the Word Problem for Finitely Presented Groups.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1987

Th Word Problem for Finitely Presented Monoids and Finite Canonical Rewriting Systems.

[BibT_eX]

[DOI]

Craig C. Squier

Proceedings of the Rewriting Techniques and Applications, 2nd International Conference, 1987

Some Results about Confluence on a Given Congruence Class.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 2nd International Conference, 1987

Groups Presented by Certain Classes of Finite Length-Reducing String-Rewriting Systems.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, 2nd International Conference, 1987

It is Decidable in Polynomial Time Whether a Monoid Presented by a Finite Weight-Reducing and Confluent Thue System is Torsion-Free.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1987

1986

The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

The Problems of Cyclic Equality and Conjugacy for Finite Complete Rewriting Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1986

Church-Rosser Thue Systems that Present Free Monoids.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

On Deciding Whether a Monoid is a Free Monoid or is a Group.

[BibT_eX]

[DOI]

Acta Informatica, 1986

1985

Complexity Results on the Conjugacy Problem for Monoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

On the Verifiability of Two-Party Algebraic Protocols.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

On the Security of Name-Stamp Protocols.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1985

A Note on Thue Systems with a Single Defining Relation.

[BibT_eX]

[DOI]

Celia Wrathall

Math. Syst. Theory, 1985

Pseudo-Natural Algorithms for the Word Problem for Finitely Presented Monoids and Groups.

[BibT_eX]

[DOI]

J. Symb. Comput., 1985

Cancellation Rules and Extended Word Problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1985

Classes of regular and context-free languages over countably infinite alphabets.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1985

Deciding Algebraic Properties of Monoids Presented by Finite Church-Rosser Thue Systems.

[BibT_eX]

[DOI]

Proceedings of the Rewriting Techniques and Applications, First International Conference, 1985

The Verifiability of Two-Party Protocols.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1985

1984

Some Undecidability Results for Non-Monadic Church-Rosser Thue Systems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1984

Finite Complete Rewriting Systems for the Jantzen Monoid and the Greendlinger Group.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1984

The Uniform Conjugacy Problem for Finite Church-Rosser Thue Systems is NP-Complete

[BibT_eX]

[DOI]

Karl Winklmann

Inf. Control., 1984

Finite Complete Rewriting Systems and the Complexity of the Word Problem.

[BibT_eX]

[DOI]

G. Bauer