Some decision problems for traces (Q4376064)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1114346
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Some decision problems for traces |
scientific article; zbMATH DE number 1114346 |
Statements
22 September 1998
0 references
independence alphabets
0 references
congruences
0 references
trace equations
0 references
decidability
0 references
monoids
0 references
0.8092733025550842
0 references
0.8033793568611145
0 references
0.7979965806007385
0 references
0.7927080392837524
0 references
0.7863204479217529
0 references
Some decision problems for traces (English)
0 references
An independence alphabet is a pair \(\langle A;I\rangle\) where \(A\) is a finite set and \(I\) is an irreflexive symmetric binary relation on \(A\) (modeling the relation: two members of \(A\) commute). The relation \(I\) induces a congruence on the monoid \(A^*\). Classes of this congruence are called traces in \(\langle A;I\rangle\). The author studies several decidability questions involving traces. A system of trace equations can be viewed as \(T=\langle A,X,S,C,I\rangle\) where \(\langle A;I\rangle\) is an independence alphabet, \(X\) is a finite set of unknowns disjoint from \(A\), \(S\) is a set of string equations in \(A\cup X\), and \(C\) is a set of commutativity equations in \(A\cup X\). A solution of \(T\) is any assignment of values to members of \(X\) which gives an \(I\)-stable solution to each equation in \(S\) and a solution to every equation from \(C\). The author proves the existence of an algorithm that tells for any given system of trace equations whether it has a solution. For the entire collection see [Zbl 0865.00035].
0 references