Sofic shifts with synchronizing presentations

DOI10.1016/0304-3975(96)00058-8zbMath0871.68137OpenAlexW2043017246MaRDI QIDQ1351451

Nataša Jonoska

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(96)00058-8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

Glider automata on all transitive sofic shifts ⋮ On the structure of a sofic shift space ⋮ Exact synchronization for finite-state sources ⋮ Determining presentations of sofic shifts ⋮ Multiplicities of covers for sofic shifts ⋮ A categorical invariant of flow equivalence of shifts ⋮ Optimal state amalgamation is NP-hard ⋮ A conjugacy invariant for reducible sofic shifts and its semigroup characterizations ⋮ Sofic Shifts via Conley Index Theory: Computing Lower Bounds on Recurrent Dynamics for Maps ⋮ Computational complexity of problems for deterministic presentations of sofic shifts ⋮ Synchronization and control in intrinsic and designed computation: An information-theoretic analysis of competing models of stochastic computation ⋮ Existence of constants in regular splicing languages

Cites Work

• On sofic systems. I
• Sofic systems and graphs
• Minimal automaton for a factorial, transitive, and rational language
• Subshifts of finite type and sofic systems
• Bounds on the number of states in encoder graphs for input-constrained channels
• A Note on Minimal Covers for Sofic Systems
• Minimal presentations for irreducible sofic shifts
• Endomorphisms and automorphisms of the shift dynamical system
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sofic shifts with synchronizing presentations