A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL

DOI10.1142/S0218196799000035MaRDI QIDQ3839881zbMATH OpenOpenAlexFDO

Authors A. N. Trahtman

Publication date 10 August 1998

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218196799000035

zbMATH Keywords

identitieslocal testability problemlocally testable semigroupsorder of local testabilitypolynomial time algorithmssets of generatorswords

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Varieties and pseudovarieties of semigroups (20M07) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1962781
• scientific article; zbMATH DE number 140486
• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• scientific article; zbMATH DE number 2050949

Cites work

• Characterizations of locally testable events
• Identities of a five-element \(0\)-simple semigroup
• The varieties of n-testable semigroups

Cited in

(10)

• Algorithms finding the order of local testability of deterministic finite automaton and estimations of the order
• Execution monitoring enforcement under memory-limitation constraints
• GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE
• On locally testable semigroups.
• scientific article; zbMATH DE number 1962781 (Why is no real title available?)
• A Local Criterion for Polynomial-Time Stratified Computations
• A probabilistic algorithm to test local algebraic observability in polynomial time
• Reducing the time complexity of testing for local threshold testability
• Local testability from words to traces, a suitable definition
• Algebraic method for generation of locally trivial tests

This page was built for publication: A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL

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