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)

Review text

A locally testable semigroup \(S\) is a semigroup with the property that for some nonnegative integer \(k\), called the order or level of local testability, two words \(u\) and \(v\) in some set of generators for \(S\) are equal in the semigroup if (1) the prefix and suffix of the words of length \(k\) coincide, and (2) the set of intermediate substrings of length \(k\) of the words coincide. The local testability problem for semigroups is, given a semigroup, to decide, if the semigroup is locally testable or not. A polynomial time algorithm for the local testability problem finding the level of local testability for semigroups is based on the description of identities of \(k\)-testable semigroups and the structure of locally testable semigroups. The first part of the algorithm solves the local testability problem. The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of order \(n^2\), where \(n\) is the order of the semigroup.

Recommendations

• A polynomial time algorithm for left [right] local testability
• A polynomial time algorithm for the local testability problem of deterministic finite automata
• 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.
• A polynomial time algorithm for left [right] local testability
• 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)