Determining presentations of sofic shifts

DOI10.1016/S0304-3975(99)00336-9MaRDI QIDQ5941276zbMATH OpenOpenAlexFDO

Authors Paul B. Trow

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00336-9

zbMATH Keywords

finite labelled directed graphsofic shift

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Sofic shifts with synchronizing presentations
• Minimal presentations for irreducible sofic shifts
• Semi-groups and graphs for sofic systems
• Sofic tree-shifts
• On the structure of covers of sofic shifts

Cites work

• A Note on Minimal Covers for Sofic Systems
• An Introduction to Symbolic Dynamics and Coding
• Covers of Non-Almost-Finite Type Sofic Systems
• Eventual factor maps and compositions of closing maps
• Lifting covers of sofic shifts
• Minimal presentations for irreducible sofic shifts
• Multiplicities of covers for sofic shifts
• Resolving maps and the dimension group for shifts of finite type
• Sofic shifts with synchronizing presentations
• Sofic systems and graphs
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts

Cited in

(8)

• Sofic shifts with synchronizing presentations
• Reducibility of covers of AFT shifts
• Computational complexity of problems for deterministic presentations of sofic shifts
• The chain relation in sofic subshifts
• On the structure of a sofic shift space
• Minimal presentations for irreducible sofic shifts
• scientific article; zbMATH DE number 841595 (Why is no real title available?)
• Optimal state amalgamation is NP-hard

This page was built for publication: Determining presentations of sofic shifts

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