Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts.

DOI10.1016/j.jpaa.2006.06.016zbMath1130.20043OpenAlexW2095413507MaRDI QIDQ869222

Alfredo Costa

Publication date: 26 February 2007

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jpaa.2006.06.016

zbMATH Keywords

conjugacysemidirect productsfactorial prolongable languagespseudovarieties of languagespseudovarieties of ordered semigroupsshift equivalencessofic subshifts

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35) Symbolic dynamics (37B10)

Related Items

A new algebraic invariant for weak equivalence of sofic subshifts ⋮ The Karoubi envelope of the mirage of a subshift ⋮ Infinite-vertex free profinite semigroupoids and symbolic dynamics. ⋮ A categorical invariant of flow equivalence of shifts ⋮ Bases for pseudovarieties closed under bideterministic product

Uses Software

• Mathematica

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On sofic systems. I
• Systèmes codés. (Coded systems)
• The Birkhoff theorem for finite algebras
• Sofic systems and graphs
• The Williams conjecture is false for irreducible subshifts
• Polynomial closure and unambiguous product
• Profinite categories and semidirect products
• Minimal automaton for a factorial, transitive, and rational language
• Subshifts of finite type and sofic systems
• Nonstandard characterization of pseudovarieties
• Profinite categories, implicit operations and pseudovarieties of categories
• A Reiterman theorem for pseudovarieties of finite first-order structures
• Locally testable semigroups
• Graph congruences and wreath products
• Locally testable languages
• Characterizations of locally testable events
• A hierarchy of shift equivalent sofic shifts
• Dynamics of implicit operations and tameness of pseudovarieties of groups
• Topological conjugacy for sofic systems
• An algorithm for sofic shift equivalence
• Williams's Conjecture is False for Reducible Subshifts
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• Algebraic decision procedures for local testability
• ORDERED CATEGORIES AND ORDERED SEMIGROUPS
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE
• SUBWORD COMPLEXITY OF PROFINITE WORDS AND SUBGROUPS OF FREE PROFINITE SEMIGROUPS
• CONJUGACY INVARIANTS OF SUBSHIFTS: AN APPROACH FROM PROFINITE SEMIGROUP THEORY
• Endomorphisms and automorphisms of the shift dynamical system