Computing the Order of a Locally Testable Automaton

DOI10.1137/S0097539791216987MaRDI QIDQ4327417zbMATH OpenFDO

Authors Sam M. Kim, Robert McNaughton

Publication date 6 April 1995

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

Full work available at URL https://doi.org/10.1137/S0097539791216987

zbMATH Keywords

locally testable language

Mathematics Subject Classification ID

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

Recommendations

• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• Optimal estimation on the order of local testability of finite automata
• scientific article; zbMATH DE number 4155920
• scientific article; zbMATH DE number 140486
• scientific article; zbMATH DE number 2081053

Cited in

(13)

• On the bound of the synchronization delay of a local automaton
• Exponential upper and lower bounds for the order of a regular language
• Optimal estimation on the order of local testability of finite automata
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• Execution monitoring enforcement under memory-limitation constraints
• Regular splicing languages and subclasses
• SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
• On free spectra of locally testable semigroup varieties
• scientific article; zbMATH DE number 4155920 (Why is no real title available?)
• Which security policies are enforceable by runtime monitors? A survey
• Identities of locally testable semigroups
• An efficient algorithm for local testability problem of finite state automata
• Reducing the time complexity of testing for local threshold testability

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

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