Search results for "Thue-systems"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
91	Thomas Deiß	Conditional Seme-Thue Systems for Presenting Monoids.	STACS	1992	DBLP DOI BibTeX RDF
66	Géraud Sénizergues	A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems.	RTA	1995	DBLP DOI BibTeX RDF	two tape finite automata, confluence, semi-Thue systems
62	P. J. Abisha, D. Gnanaraj Thomas, K. G. Subramanian 0001	Public Key Cryptosystems Based on Free Partially Commutative Monoids and Groups.	INDOCRYPT	2003	DBLP DOI BibTeX RDF	Finitely Presented Groups, Free Partially Commutative Monoids, Thue Systems, Public Key Cryptosystem, Word Problem, Zero Knowledge Protocol
56	Robert McNaughton, Paliath Narendran, Friedrich Otto	Church-Rosser Thue systems and formal languages.	J. ACM	1988	DBLP DOI BibTeX RDF
56	Volker Diekert	Transitive Orientations, Möbius Functions, and Complete Semi-Thue Systems for Free Partially Commutative Monoids.	ICALP	1988	DBLP DOI BibTeX RDF
56	Wojciech Moczydlowski, Alfons Geser	Termination of Single-Threaded One-Rule Semi-Thue Systems.	RTA	2005	DBLP DOI BibTeX RDF	uniform termination, one-rule, single-rule, single-threaded, well-behaved, termination, string rewriting, semi-Thue system
56	Géraud Sénizergues	Some Undecidable Termination Problems for Semi-Thue Systems (Abstract).	RTA	1993	DBLP DOI BibTeX RDF
53	Volker Claus, H. Walter	Zerlegungen von Semi-Thue-Systemen.	Computing	1969	DBLP DOI BibTeX RDF
45	Françoise Levy-dit-Vehel, Ludovic Perret	Attacks on Public Key Cryptosystems Based on Free Partially Commutative Monoids and Groups.	INDOCRYPT	2004	DBLP DOI BibTeX RDF	Thue Systems, Finitely Presented Groups, Free Partially Commutative Monoids, Homomorphic Mappings, Word Problem, Public Key Cryptanalysis
45	Géraud Sénizergues	On the Termination Problem for One-Rule Semi-Thue System.	RTA	1996	DBLP DOI BibTeX RDF	rational monoid, automatic structure, termination, finite automata, semi-Thue systems
41	Friedrich Otto	The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems.	Theor. Comput. Sci.	1986	DBLP DOI BibTeX RDF
41	Markus Lohrey	Word Problems and Confluence Problems for Restricted Semi-Thue Systems.	RTA	2000	DBLP DOI BibTeX RDF
39	Christopher Lynch	The Unification Problem for One Relation Thue Systems.	AISC	1998	DBLP DOI BibTeX RDF
38	Markus Lohrey	Complexity Results for Confluence Problems.	MFCS	1999	DBLP DOI BibTeX RDF
37	Rakesh M. Verma, Michaël Rusinowitch, Denis Lugiez	Algorithms and Reductions for Rewriting Problems.	RTA	1998	DBLP DOI BibTeX RDF
35	Friedrich L. Bauer	Syntaktische Struktur formaler und natürlicher Sprachen.	Computing	1966	DBLP DOI BibTeX RDF
35	Markus Lohrey	Word Problems for 2-Homogeneous Monoids and Symmetric Logspace.	MFCS	2001	DBLP DOI BibTeX RDF
27	Alfons Geser, Dieter Hofbauer, Johannes Waldmann	Termination Proofs for String Rewriting Systems via Inverse Match-Bounds.	J. Autom. Reason.	2005	DBLP DOI BibTeX RDF	match-bounded, inhibitor, termination, normalization, reachability, regular languages, context-free languages, semi-Thue systems, string rewriting systems
27	Géraud Sénizergues	An Effective Version of Stallings' Theorem in the Case of Context-Free Groups.	ICALP	1993	DBLP DOI BibTeX RDF	context-free groups, Thue-systems, graph of groups, complexity, Cayley graph, pushdown automata
23	Ronald V. Book	Thue Systems as Rewriting Systems.	J. Symb. Comput.	1987	DBLP DOI BibTeX RDF
23	Ronald V. Book	Thue Systems as Rewriting Systems.	RTA	1985	DBLP DOI BibTeX RDF
21	Alexey L. Talambutsa	On Subquadratic Derivational Complexity of Semi-Thue Systems.	CSR	2020	DBLP DOI BibTeX RDF
21	Vesa Halava	Deterministic Semi-Thue Systems and Variants of Post Correspondence Problem.	WORDS	2013	DBLP DOI BibTeX RDF
21	Michel Latteux, Yves Roos	On One-Rule Grid Semi-Thue Systems.	Fundam. Informaticae	2012	DBLP DOI BibTeX RDF
21	Colm Ó'Dúnlaing, Natalie Schluter	A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
21	François Nicolas	(Generalized) Post Correspondence Problem and semi-Thue systems	CoRR	2008	DBLP BibTeX RDF
21	Yuri V. Matiyasevich, Géraud Sénizergues	Decision problems for semi-Thue systems with a few rules.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
21	Robert McNaughton	Semi-Thue Systems with an Inhibitor.	J. Autom. Reason.	2001	DBLP DOI BibTeX RDF
21	Géraud Sénizergues	A Polynomial Algorithm Testing Partial Confluence of Basic Semi-Thue Systems.	Theor. Comput. Sci.	1998	DBLP DOI BibTeX RDF
21	Robert McNaughton	Book's Impact on the Theory of Thue Systems - Abstract.	Advances in Algorithms, Languages, and Complexity	1997	DBLP BibTeX RDF
21	Louxin Zhang, Lian Li, Jinzhao Wu	On the descriptive power of special Thue systems.	Discret. Math.	1996	DBLP DOI BibTeX RDF
21	Winfried Kurth	One-Rule Semi-Thue Systems with Loops of Length One, Two or Three.	RAIRO Theor. Informatics Appl.	1996	DBLP DOI BibTeX RDF
21	Yuri V. Matiyasevich, Géraud Sénizergues	Decision Problems for Semi-Thue Systems with a Few Rules.	LICS	1996	DBLP DOI BibTeX RDF
21	Géraud Sénizergues	Some Undecidable Termination Problems for Semi-Thue Systems.	Theor. Comput. Sci.	1995	DBLP DOI BibTeX RDF
21	Yuri V. Matiyasevich	Word Problem for Thue Systems with a Few Relations.	Term Rewriting	1993	DBLP DOI BibTeX RDF
21	Rani Siromoney, D. Gnanaraj Thomas, K. G. Subramanian 0001, V. Rajkumar Dare	Thue Systems and DNA - A Learning Algorithm for a Subclass.	ALT	1993	DBLP DOI BibTeX RDF
21	Chee-Keng Yap	A New Lower Bound Construction for Commutative Thue Systems with aApplications.	J. Symb. Comput.	1991	DBLP DOI BibTeX RDF
21	Ronald V. Book	A Note on Confluent Thue Systems.	IWWERT	1990	DBLP DOI BibTeX RDF
21	Celia Wrathall	Confluence of One-Rule Thue Systems.	IWWERT	1990	DBLP DOI BibTeX RDF
21	Paliath Narendran, Friedrich Otto	Some Polynomial-Time Algorithms for Finite Monadic Church-Rosser Thue Systems.	Theor. Comput. Sci.	1989	DBLP DOI BibTeX RDF
21	Paliath Narendran, Friedrich Otto	Preperfectness is Undecidable for Thue Systems Containing Only Length-Reducing Rules and a Single Commutation Rule.	Inf. Process. Lett.	1988	DBLP DOI BibTeX RDF
21	Paliath Narendran, Friedrich Otto	Elements of Finite Order for Finite Weight-Reducing and Confluent Thue Systems.	Acta Informatica	1988	DBLP DOI BibTeX RDF
21	W. Bucher	A note on regular classes in special Thue systems.	Discret. Appl. Math.	1988	DBLP DOI BibTeX RDF
21	Klaus Madlener, Friedrich Otto	Commutativity in Groups Presented By Finite Church-Rosser Thue Systems.	RAIRO Theor. Informatics Appl.	1988	DBLP DOI BibTeX RDF
21	Volker Diekert	Some Remarks on Presentations by Finite Church-Rosser Thue Systems.	STACS	1987	DBLP DOI BibTeX RDF
21	Volker Diekert	Complete Semi-Thue Systems for Abelian Groups.	Theor. Comput. Sci.	1986	DBLP DOI BibTeX RDF
21	Paliath Narendran	On the Equivalence Problem for Regular Thue Systems.	Theor. Comput. Sci.	1986	DBLP DOI BibTeX RDF
21	Dung T. Huynh	A Superexponential Lower Bound for Gröbner Bases and Church-Rosser Commutative Thue Systems	Inf. Control.	1986	DBLP DOI BibTeX RDF
21	Friedrich Otto	Church-Rosser Thue Systems that Present Free Monoids.	SIAM J. Comput.	1986	DBLP DOI BibTeX RDF
21	Deepak Kapur, Paliath Narendran, Mukkai S. Krishnamoorthy, Robert McNaughton	The Church-Rosser Property and Special Thue Systems.	Theor. Comput. Sci.	1985	DBLP DOI BibTeX RDF
21	Deepak Kapur, Mukkai S. Krishnamoorthy, Robert McNaughton, Paliath Narendran	An O(\|T\|3) Algorithm for Testing the Church-Rosser Property of Thue Systems.	Theor. Comput. Sci.	1985	DBLP DOI BibTeX RDF
21	Luquan Pan	On Reduced Thue Systems.	Math. Syst. Theory	1985	DBLP DOI BibTeX RDF
21	Friedrich Otto, Celia Wrathall	A Note on Thue Systems with a Single Defining Relation.	Math. Syst. Theory	1985	DBLP DOI BibTeX RDF
21	Deepak Kapur, Paliath Narendran	The Knuth-Bendix Completion Procedure and Thue Systems.	SIAM J. Comput.	1985	DBLP DOI BibTeX RDF
21	Friedrich Otto	Deciding Algebraic Properties of Monoids Presented by Finite Church-Rosser Thue Systems.	RTA	1985	DBLP DOI BibTeX RDF
21	Matthias Jantzen, Manfred Kudlek	Homomorphic Images of Sentential Form Languages Defined by Semi-Thue Systems.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
21	Friedrich Otto	Some Undecidability Results for Non-Monadic Church-Rosser Thue Systems.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
21	Paliath Narendran, Robert McNaughton	The Undecidability of the Preperfectness of Thue Systems.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
21	Ronald V. Book, Craig C. Squier	Almost all one-rule thue systems have decidable word problems.	Discret. Math.	1984	DBLP DOI BibTeX RDF
21	Ronald V. Book	Homogeneous Thue systems and the Church-Rosser property.	Discret. Math.	1984	DBLP DOI BibTeX RDF
21	Paliath Narendran, Friedrich Otto, Karl Winklmann	The Uniform Conjugacy Problem for Finite Church-Rosser Thue Systems is NP-Complete	Inf. Control.	1984	DBLP DOI BibTeX RDF
21	Matthias Jantzen	Thue Systems and the Church-Rosser Property.	MFCS	1984	DBLP DOI BibTeX RDF
21	Paliath Narendran	Church-Rosser and related Thue systems.		1984	RDF
21	Colm Ó'Dúnlaing	Undecidable questions related to Church-Rosser Thue systems.	Theor. Comput. Sci.	1983	DBLP DOI BibTeX RDF
21	Colm Ó'Dúnlaing	Infinite Regular Thue Systems.	Theor. Comput. Sci.	1983	DBLP DOI BibTeX RDF
21	Ronald V. Book	A Note on Special Thue Systems with a Single Defining Relation.	Math. Syst. Theory	1983	DBLP DOI BibTeX RDF
21	Ronald V. Book, Matthias Jantzen, Celia Wrathall	Monadic Thue Systems.	Theor. Comput. Sci.	1982	DBLP DOI BibTeX RDF
21	Ronald V. Book	Confluent and Other Types of Thue Systems.	J. ACM	1982	DBLP DOI BibTeX RDF
21	Colm Ó'Dúnlaing	Finite and infinite regular thue systems.		1981	RDF
21	Ronald V. Book, Matthias Jantzen, Burkhard Monien, Colm Ó'Dúnlaing, Celia Wrathall	On the Complexity of Word Problems in Certain Thue Systems (Preliminary Report).	MFCS	1981	DBLP DOI BibTeX RDF
21	Egon Börger, Hans Kleine Büning	The R. E. Complexity of Decision Problems for Commutative Semi-Thue Systems With Recursive Rule Set.	Math. Log. Q.	1980	DBLP DOI BibTeX RDF
21	Nguyen Xuan My	Some Classes of Semi-Thue Systems.	J. Inf. Process. Cybern.	1980	DBLP BibTeX RDF
21	Charles E. Hughes	Many-one Degrees Associated with Semi-Thue Systems.	J. Comput. Syst. Sci.	1973	DBLP DOI BibTeX RDF
21	Walter S. Brainerd	Semi-Thue Systems and Representations of Trees	SWAT	1969	DBLP DOI BibTeX RDF
20	Kai Salomaa	Decidability of Confluence and Termination of Monadic Term Rewriting Systems.	RTA	1991	DBLP DOI BibTeX RDF
20	Volker Diekert	Word Problems over TRaces Which are Solvable in Linear Time.	STACS	1989	DBLP DOI BibTeX RDF
19	Volker Diekert	On the Knuth-Bendix Completion for Concurrent Processes.	ICALP	1987	DBLP DOI BibTeX RDF
19	Philippe le Chenadec	Canonical Forms in Finitely Presented Algebras.	CADE	1984	DBLP DOI BibTeX RDF	Finitely Presented Algebras, Completion Procedures, Rewriting Systems, Word Problem
18	Dietrich Kuske, Markus Lohrey	Decidable First-Order Theories of One-Step Rewriting in Trace Monoids.	Theory Comput. Syst.	2005	DBLP DOI BibTeX RDF
18	Dietrich Kuske, Markus Lohrey	On the Theory of One-Step Rewriting in Trace Monoids.	ICALP	2002	DBLP DOI BibTeX RDF
18	Christian Delhommé, Teodor Knapik, D. Gnanaraj Thomas	Using Transitive-Closure Logic for Deciding Linear Properties of Monoids.	MFCS	2003	DBLP DOI BibTeX RDF	monoid presentations, transitive closure logic, string rewriting
18	Géraud Sénizergues	Some Applications of the Decidability of DPDA's Equivalence.	MCU	2001	DBLP DOI BibTeX RDF