article

Some undecidability results for finitely generated Thue congruences on a two-letter alphabet

Authors:

Klaus Madlener,

Friedrich OttoAuthors Info & Claims

Fundamenta Informaticae, Volume 30, Issue 1

Pages 31 - 44

Published: 01 April 1997 Publication History

Abstract

No abstract available.

Cited By

View all

LaViola JZeleznik RMcMains SSloan P(2007)MathPad2ACM SIGGRAPH 2007 courses10.1145/1281500.1281557(46-es)Online publication date: 5-Aug-2007
https://dl.acm.org/doi/10.1145/1281500.1281557
LaViola JZeleznik RFinnegan JShreiner D(2006)MathPad2ACM SIGGRAPH 2006 Courses10.1145/1185657.1185794(33-es)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1185657.1185794
LaViola JZeleznik R(2004)MathPad2ACM SIGGRAPH 2004 Papers10.1145/1186562.1015741(432-440)Online publication date: 8-Aug-2004
https://dl.acm.org/doi/10.1145/1186562.1015741
Show More Cited By

Index Terms

Some undecidability results for finitely generated Thue congruences on a two-letter alphabet
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Computer algebra systems
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Some Undecidability Results For Finitely Generated Thue Congruences On A Two-Letter Alphabet

Following the course set by A. Markov (1951), S. Adjan (1958), and M. Rabin (1958), C. Ó'Dúnlaing (1983) has shown that certain properties of finitely generated Thue congruences are undecidable in general. Here we prove that many of these undecidability ...
About some overlap-free morphisms on a n-letter alphabet
Third international workshop on descriptional complexity of automata, grammars and related structures

In 1912, the Norwegian mathematician Axel Thue was the first to describe an overlapfree binary infinite word. This word was generated by a morphism which is called, since the works of Morse, the Thue-Morse morphism.Here we study morphisms, generalizing ...
Classification of regular languages by congruences

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Fundamenta Informaticae Volume 30, Issue 1

April 1997

118 pages

ISSN:0169-2968

Editor:
A. Skowron
Warsaw Univ., Warsaw, Poland

Issue’s Table of Contents

Publisher

IOS Press

Netherlands

Publication History

Published: 01 April 1997

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

LaViola JZeleznik RMcMains SSloan P(2007)MathPad2ACM SIGGRAPH 2007 courses10.1145/1281500.1281557(46-es)Online publication date: 5-Aug-2007
https://dl.acm.org/doi/10.1145/1281500.1281557
LaViola JZeleznik RFinnegan JShreiner D(2006)MathPad2ACM SIGGRAPH 2006 Courses10.1145/1185657.1185794(33-es)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1185657.1185794
LaViola JZeleznik R(2004)MathPad2ACM SIGGRAPH 2004 Papers10.1145/1186562.1015741(432-440)Online publication date: 8-Aug-2004
https://dl.acm.org/doi/10.1145/1186562.1015741
LaViola JZeleznik R(2004)MathPad2ACM Transactions on Graphics10.1145/1015706.101574123:3(432-440)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1145/1015706.1015741
Katsura MKobayashi Y(2003)Undecidable properties of monoids with word problem solvable in linear timeTheoretical Computer Science10.1016/S0304-3975(01)00275-4290:3(1301-1316)Online publication date: 3-Jan-2003
https://dl.acm.org/doi/10.1016/S0304-3975%2801%2900275-4
Verma RRusinowitch MLugiez D(2001)Algorithms and Reductions for Rewriting ProblemsFundamenta Informaticae10.5555/2372167.237217246:3(257-276)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.5555/2372167.2372172
Verma RRusinowitch MLugiez D(2001)Algorithms and Reductions for Rewriting ProblemsFundamenta Informaticae10.5555/1219995.122000046:3(257-276)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.5555/1219995.1220000

Abstract

Cited By

Index Terms

Recommendations

Some Undecidability Results For Finitely Generated Thue Congruences On A Two-Letter Alphabet

About some overlap-free morphisms on a n-letter alphabet

Classification of regular languages by congruences

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations