Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order

DOI10.1016/S0304-3975(99)00191-7MaRDI QIDQ1978707zbMATH OpenFDO

Authors A. N. Trahtman

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Varieties and pseudovarieties of semigroups (20M07)

Recommendations

• Computing the Order of a Locally Testable Automaton
• scientific article; zbMATH DE number 4155920
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• scientific article; zbMATH DE number 140486
• Optimal estimation on the order of local testability of finite automata
• scientific article; zbMATH DE number 2081053
• An efficient algorithm for local testability problem of finite state automata
• General Algorithms for Testing the Ambiguity of Finite Automata
• A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL
• Partially ordered automata and piecewise testability

Cites work

• scientific article; zbMATH DE number 988805 (Why is no real title available?)
• scientific article; zbMATH DE number 4155920 (Why is no real title available?)
• scientific article; zbMATH DE number 3975234 (Why is no real title available?)
• scientific article; zbMATH DE number 3654376 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1300962 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• Characterizations of locally testable events
• Computing the Order of a Locally Testable Automaton
• Depth-First Search and Linear Graph Algorithms
• Locally testable languages
• Locally testable semigroups
• Lower Bound of the Number of Threshold Functions
• Regular locally testable semigroups as semigroups of quasi-ideals
• The Theory of Definite Automata
• The varieties of n-testable semigroups

Cited in

(11)

• scientific article; zbMATH DE number 140486 (Why is no real title available?)
• scientific article; zbMATH DE number 4047135 (Why is no real title available?)
• Reducing the time complexity of testing for local threshold testability
• Computing the Order of a Locally Testable Automaton
• scientific article; zbMATH DE number 2081053 (Why is no real title available?)
• scientific article; zbMATH DE number 1962784 (Why is no real title available?)
• scientific article; zbMATH DE number 4155920 (Why is no real title available?)
• An efficient algorithm for local testability problem of finite state automata
• GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE
• A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL
• Optimal estimation on the order of local testability of finite automata

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order

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