Piecewise and local threshold testability of DFA

DOI10.1007/3-540-44669-9_33MaRDI QIDQ4782722zbMATH OpenFDO

Authors A. N. Trahtman

Publication date 2 December 2002

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2138/21380347

zbMATH Keywords

algorithmautomatonlocally testablelocally threshold testablepiecewise testablesyntactic semigrouptransition graph

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• An algorithm to verify local threshold testability of deterministic finite automata
• 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
• scientific article; zbMATH DE number 2050939
• On separation by locally testable and locally threshold testable languages
• Separating regular languages by locally testable and locally threshold testable languages
• scientific article; zbMATH DE number 4155920
• An efficient algorithm for local testability problem of finite state automata
• A new algorithm for testing if a regular language is locally threshold testable
• scientific article; zbMATH DE number 2050949

Cited in

(15)

• Separability by piecewise testable languages is \textsc{PTime}-complete
• On Boolean combinations forming piecewise testable languages
• A new algorithm for testing if a regular language is locally threshold testable
• On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs
• On the complexity of k-piecewise testability and the depth of automata
• scientific article; zbMATH DE number 4155920 (Why is no real title available?)
• Reducing the time complexity of testing for local threshold testability
• A package TESTAS for checking some kinds of testability
• An algorithm to verify local threshold testability of deterministic finite automata
• Piecewise testable languages and nondeterministic automata
• Partially ordered automata and piecewise testability
• Testing Simon's congruence
• Alternative automata characterization of piecewise testable languages
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Reducing the time complexity of testing for local threshold testability

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Piecewise and local threshold testability of DFA

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