A polynomial time algorithm for the local testability problem of deterministic finite automata

DOI10.1109/12.93741zbMATH Open1395.68171OpenAlexW2130750623MaRDI QIDQ5375412FDOQ5375412

Authors: Sam M. Kim, Robert McNaughton, Robert McCloskey 

Publication date: 14 September 2018

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/12.93741

Mathematics Subject Classification ID

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

Cited In (18)

• Execution monitoring enforcement under memory-limitation constraints
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducing the time complexity of testing for local threshold testability
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• Families of locally testable languages
• Local testability from words to traces, a suitable definition
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• Title not available (Why is that?)
• Free profinite locally idempotent and locally commutative semigroups
• Checking whether an automaton is monotonic is NP-complete
• Which security policies are enforceable by runtime monitors? A survey
• Title not available (Why is that?)
• An efficient algorithm for local testability problem of finite state automata
• Algebraic method for generation of locally trivial tests
• A probabilistic algorithm to test local algebraic observability in polynomial time
• LANGAGE: A Maple package for automaton characterization of regular languages
• Optimal estimation on the order of local testability of finite automata

This page was built for publication: A polynomial time algorithm for the local testability problem of deterministic finite automata

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