Computing the Order of a Locally Testable Automaton

DOI10.1137/S0097539791216987zbMath0830.68065MaRDI QIDQ4327417

Robert McNaughton, Sam M. Kim

Publication date: 6 April 1995

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

locally testable language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (11)

An efficient algorithm for local testability problem of finite state automata ⋮ Which security policies are enforceable by runtime monitors? A survey ⋮ Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order ⋮ SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES ⋮ Execution monitoring enforcement under memory-limitation constraints ⋮ Regular splicing languages and subclasses ⋮ Reducing the time complexity of testing for local threshold testability ⋮ Identities of locally testable semigroups ⋮ ON FREE SPECTRA OF LOCALLY TESTABLE SEMIGROUP VARIETIES ⋮ On the bound of the synchronization delay of a local automaton ⋮ Optimal estimation on the order of local testability of finite automata

This page was built for publication: Computing the Order of a Locally Testable Automaton