An algorithm for sofic shift equivalence

DOI10.1017/S0143385700005617MaRDI QIDQ3828207zbMATH OpenOpenAlexFDO

Authors Ki Hang Kim, Fred Roush

Publication date 1990

Published in Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0143385700005617

zbMATH Keywords

algorithmcongruencesdecidablesemigroup of transformation matricessemigroup semiringsofic shift equivalence

Mathematics Subject Classification ID

Semirings (16Y60) Free semigroups, generators and relations, word problems (20M05) Semigroup rings, multiplicative semigroups of rings (20M25) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 14993
• Flow equivalence of sofic shifts
• scientific article; zbMATH DE number 1099662
• THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE
• A hierarchy of shift equivalent sofic shifts

Cited in

(16)

• Flow equivalence of sofic shifts
• Computing degree and class degree
• A hierarchy of shift equivalent sofic shifts
• A categorical invariant of flow equivalence of shifts
• A new algebraic invariant for weak equivalence of sofic subshifts
• The publications of Ki Hang Kim
• The work of Kim and Roush in symbolic dynamics
• Resolving extensions of finitely presented systems
• Path methods for strong shift equivalence of positive matrices
• Decidability of epimorphisms of dimension groups and certain modules
• Solution of Two Conjectures in Symbolic Dynamics
• scientific article; zbMATH DE number 14993 (Why is no real title available?)
• scientific article; zbMATH DE number 706764 (Why is no real title available?)
• THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE
• Completing codes in a sofic shift
• Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts.

This page was built for publication: An algorithm for sofic shift equivalence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3828207)