scientific article; zbMATH DE number 789389

Publication date: 23 August 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

convergence Turing machines public key cryptosystems confluence pushdown automata string-rewriting systems Church- Rosser property finite state acceptors

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Grammars and rewriting systems (68Q42)

Related Items (only showing first 100 items - show all)

On the data complexity of consistent query answering over graph databases ⋮ A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods ⋮ Introduction to Probabilistic Concurrent Systems ⋮ Finite derivation type for Rees matrix semigroups ⋮ Model Checking Procedural Programs ⋮ A complete characterization of termination of 0p 1q→1r 0s ⋮ Some independence results for equational unification ⋮ The first-order theory of one-step rewriting is undecidable ⋮ On the termination problem for one-rule semi-Thue system ⋮ FDT is undecidable for finitely presented monoids with solvable word problems ⋮ Rational subsets of partially reversible monoids ⋮ Ends for subsemigroups of finite index. ⋮ Algebraic coherent confluence and higher globular Kleene algebras ⋮ Fixed points of endomorphisms of certain free products ⋮ Learning deterministic context free grammars: the Omphalos competition ⋮ LARS: a learning algorithm for rewriting systems ⋮ Reduction relations for monoid semirings ⋮ Finite derivation type for large ideals. ⋮ Monoid presentations of groups by finite special string-rewriting systems ⋮ Reduction operators and completion of rewriting systems ⋮ Gröbner bases of associative algebras and the Hochschild cohomology ⋮ \(\mathrm C^*\)-algebras of right LCM one-relator monoids and Artin-Tits monoids of finite type ⋮ The word matching problem is undecidable for finite special string-rewriting systems that are confluent ⋮ The isomorphism problem for finite extensions of free groups is in PSPACE ⋮ Takahasi semigroups ⋮ Crossed product of infinite groups and complete rewriting systems ⋮ Ascending chain conditions on right ideals of semigroups ⋮ Reachability analysis of pushdown automata: Application to model-checking ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS ⋮ Order Reconfiguration under Width Constraints ⋮ On the word problem for weakly compressible monoids ⋮ DNA origami words, graphical structures and their rewriting systems ⋮ Finite presentability and isomorphism of Cayley graphs of monoids ⋮ Equational Theorem Proving for Clauses over Strings ⋮ A hierarchy of deterministic top-down tree transformations ⋮ On the word problem for free products of semigroups and monoids ⋮ Church-Rosser codes ⋮ Growth of positive words and lower bounds of the growth rate for Thompson’s groups F(p) ⋮ On groups presented by inverse-closed finite confluent length-reducing rewriting systems ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Word-mappings of level 2 ⋮ Complete rewriting system for the Schützenberger product of n groups ⋮ GROWTHS OF ENDOMORPHISMS OF FINITELY GENERATED SEMIGROUPS ⋮ On Regularity-Preservation by String-Rewriting Systems ⋮ Polycyclic and Bicyclic Valence Automata ⋮ Proving convergence of self-stabilizing systems using first-order rewriting and regular languages ⋮ The monoids of the patience sorting algorithm ⋮ Noncommutative Gröbner Bases: Applications and Generalizations ⋮ A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata ⋮ Gröbner-Shirshov bases for some braid groups. ⋮ String rewriting for double coset systems. ⋮ An introduction to presentations of monoid acts: quotients and subacts ⋮ Compressed Membership in Automata with Compressed Labels ⋮ Theorem proving with group presentations: Examples and questions ⋮ Algebra and automated deduction ⋮ The B B Newman spelling theorem ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ A solution of the word problem for free \(^*\)-regular semigroups ⋮ Efficient algorithms for highly compressed data: the word problem in generalized Higman groups is in P ⋮ Computing by commuting. ⋮ Symbolic model checking with rich assertional languages ⋮ On interreduction of semi-complete term rewriting systems ⋮ An automated approach to the Collatz conjecture ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Convergent presentations and polygraphic resolutions of associative algebras ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sequential monotonicity for restarting automata ⋮ The symmetric group given by a Gröbner basis ⋮ Unnamed Item ⋮ Uniform decision problems for automatic semigroups. ⋮ A Hierarchy of Transducing Observer Systems ⋮ Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups ⋮ Bounded Hairpin Completion ⋮ Free idempotent generated semigroups over bands and biordered sets with trivial products ⋮ Presentations of the Schützenberger Product of n Groups ⋮ On a graph connecting hyperbinary expansions ⋮ A countable family of finitely presented infinite congruence-free monoids ⋮ Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System ⋮ On Finite Complete Presentations and Exact Decompositions of Semigroups ⋮ On prefixal one-rule string rewrite systems ⋮ Polygraphs of finite derivation type ⋮ Lambda-confluence for context rewriting systems ⋮ An almost-confluent congruential language which is not Church-Rosser congruential ⋮ Modeling Pointer Redirection as Cyclic Term-graph Rewriting ⋮ The ℛ-height of semigroups and their bi-ideals ⋮ A finiteness condition for rewriting systems ⋮ On termination of confluent one-rule string-rewriting systems ⋮ Monads, partial evaluations, and rewriting ⋮ Peg-solitaire, string rewriting systems and finite automata ⋮ A Lyndon's identity theorem for one-relator monoids ⋮ Codes modulo finite monadic string-rewriting systems ⋮ Crystal monoids \& crystal bases: rewriting systems and biautomatic structures for plactic monoids of types \(A_{n}\), \(B_{n}\), \(C_{n}\), \(D_{n}\), and \(G_{2}\) ⋮ Decision problems for word-hyperbolic semigroups ⋮ Decidability and independence of conjugacy problems in finitely presented monoids ⋮ Termination of \(\{aa\rightarrow bc,bb\rightarrow ac,cc\rightarrow ab\}\) ⋮ A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems ⋮ Isoperimetric functions for graph products ⋮ Termination proofs for string rewriting systems via inverse match-bounds

This page was built for publication: