An algorithm to verify local threshold testability of deterministic finite automata

DOI10.1007/3-540-45526-4_15MaRDI QIDQ4474160zbMATH OpenFDO

Authors A. N. Trahtman

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.10654, http://link.springer.de/link/service/series/0558/bibs/2214/22140164.htm

zbMATH Keywords

algorithmdeterministic finite automatonlocally threshold testablesemigroup

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A polynomial time algorithm for the local testability problem of deterministic finite automata
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• An efficient algorithm for local testability problem of finite state automata
• Piecewise and local threshold testability of DFA
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• scientific article; zbMATH DE number 4155920
• A new algorithm for testing if a regular language is locally threshold testable
• scientific article; zbMATH DE number 2050939
• General Algorithms for Testing the Ambiguity of Finite Automata
• Separating regular languages by locally testable and locally threshold testable languages

Cited in

(17)

• Families of locally testable languages
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• A new algorithm for testing if a regular language is locally threshold testable
• Execution monitoring enforcement under memory-limitation constraints
• STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
• scientific article; zbMATH DE number 4155920 (Why is no real title available?)
• Reducing the time complexity of testing for local threshold testability
• scientific article; zbMATH DE number 4047135 (Why is no real title available?)
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• Computing the Order of a Locally Testable Automaton
• A polynomial time algorithm for left [right] local testability
• scientific article; zbMATH DE number 2050939 (Why is no real title available?)
• scientific article; zbMATH DE number 1472161 (Why is no real title available?)
• Which security policies are enforceable by runtime monitors? A survey
• Piecewise and local threshold testability of DFA
• An efficient algorithm for local testability problem of finite state automata
• Reducing the time complexity of testing for local threshold testability

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: An algorithm to verify local threshold testability of deterministic finite automata

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