Strict local testability with consensus equals regularity

DOI10.1007/978-3-642-31606-7_10MaRDI QIDQ2914699zbMATH OpenOpenAlexFDO

Authors Stefano Crespi Reghizzi, Pierluigi San Pietro

Publication date 20 September 2012

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31606-7_10

zbMATH Keywords

consensual languagecontext-freecontext-sensitivecounter machineformal languageshomomorphic characterizationlocal languageMedvedev theoremnon-countingregular languagesliding-windowstrict local testability

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Strict local testability with consensus equals regularity, and other properties
• Consensual Definition of Languages by Regular Sets
• Consensual languages and matching finite-state computations
• Some variations on the notion of locally testable language
• Families of locally testable languages

Cited in

(8)

• Testing equality under the local broadcast model
• Consensual languages and matching finite-state computations
• Consensus game acceptors
• Consensual Definition of Languages by Regular Sets
• Consensus game acceptors and iterated transductions
• From Local to Robust Testing via Agreement Testing
• Counter machines, Petri nets, and consensual computation
• Strict local testability with consensus equals regularity, and other properties

This page was built for publication: Strict local testability with consensus equals regularity

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