Local testability from words to traces, a suitable definition

DOI10.1016/J.TCS.2016.06.023zbMath1358.68169OpenAlexW2470388261MaRDI QIDQ728279

Giovanna Guaiana

Publication date: 19 December 2016

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.023

zbMATH Keywords

local testabilityrecognizabilitytrace languagetrace monoidquasi-idealstar-free language

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logical definability on infinite traces
• Asynchronous mappings and asynchronous cellular automata
• Permutation rewriting and algorithmic verification
• Theory of traces
• Languages and scanners
• Polynomial operations and hierarchies of concatenation
• Logically defined subsets of \(\mathbb{N}{}^ k\)
• Star-free trace languages
• Polynomial closure and unambiguous product
• Combinatorial problems of commutation and rearrangements
• Rational sets in commutative monoids
• Locally testable languages
• Characterizations of locally testable events
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Algebraic decision procedures for local testability
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• On finite monoids having only trivial subgroups
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• A Star Operation for Star-Free Trace Languages

This page was built for publication: Local testability from words to traces, a suitable definition