A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL

DOI10.1142/S0218196799000035zbMath0931.20046OpenAlexW2015523519MaRDI QIDQ3839881

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

wordsidentitiespolynomial time algorithmssets of generatorslocally testable semigroupslocal testability problemorder of local testability

Mathematics Subject Classification ID

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

Related Items (3)

GROUPS WHOSE GEODESICS ARE LOCALLY TESTABLE ⋮ Execution monitoring enforcement under memory-limitation constraints ⋮ Reducing the time complexity of testing for local threshold testability

Cites Work

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

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