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

DOI10.1016/S0304-3975(99)00191-7zbMath0938.68055MaRDI QIDQ1978707

A. N. Trahtman

Publication date: 4 June 2000

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

Mathematics Subject Classification ID

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

Related Items (1)

Reducing the time complexity of testing for local threshold testability

Uses Software

• LANGAGE

Cites Work

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

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