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

DOI10.1016/S0304-3975(99)00191-7zbMATH Open0938.68055MaRDI QIDQ1978707FDOQ1978707

A. N. Trahtman

Publication date: 4 June 2000

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

Recommendations

• Computing the Order of a Locally Testable Automaton
• scientific article
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• scientific article
• 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
• scientific article; zbMATH DE number 7350780

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Depth-First Search and Linear Graph Algorithms
• Characterizations of locally testable events
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the Order of a Locally Testable Automaton
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• The Theory of Definite Automata
• Locally testable semigroups
• Locally testable languages
• Regular locally testable semigroups as semigroups of quasi-ideals
• The varieties of n-testable semigroups
• Lower Bound of the Number of Threshold Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducing the time complexity of testing for local threshold testability
• Computing the Order of a Locally Testable Automaton
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)