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

DOI10.1109/12.93741zbMath1395.68171OpenAlexW2130750623MaRDI QIDQ5375412

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

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

Related Items (11)

Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ 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 ⋮ Execution monitoring enforcement under memory-limitation constraints ⋮ Reducing the time complexity of testing for local threshold testability ⋮ Free profinite locally idempotent and locally commutative semigroups ⋮ Local testability from words to traces, a suitable definition ⋮ Families of locally testable languages ⋮ Optimal estimation on the order of local testability of finite automata ⋮ LANGAGE: A Maple package for automaton characterization of regular languages

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