TESTAS

We implement a set of procedures for deciding whether or not a language given by its minimal automaton or by its syntactic semigroup is locally testable, right or left locally testable, threshold locally testable, strictly locally testable, or piecewise testable. The bounds on order of local testability of transition graph and order of local testability of transition semigroup are also found. For given k, the k-testability of transition graph is verified. Some new effective polynomial time algorithms are used. These algorithms have been implemented as a C/C ++ package


References in zbMATH (referenced in 18 articles , 1 standard article )

Showing results 1 to 18 of 18.
Sorted by year (citations)

  1. Vorel, Vojtěch; Roman, Adam: Complexity of road coloring with prescribed reset words (2019)
  2. Don, Henk; Zantema, Hans: Finding DFAs with maximal shortest synchronizing word length (2017)
  3. Kisielewicz, Andrzej; Kowalski, Jakub; Szykuła, Marek: Experiments with synchronizing automata (2016)
  4. Kisielewicz, Andrzej; Kowalski, Jakub; Szykuła, Marek: Computing the shortest reset words of synchronizing automata (2015)
  5. Trahtman, A. N.: An algorithm for road coloring (2012)
  6. Chmiel, Krzysztof; Roman, Adam: COMPAS -- a computing package for synchronization (2011)
  7. Steinberg, Benjamin: The Černý conjecture for one-cluster automata with prime length cycle (2011)
  8. Trahtman, A. N.: An algorithm for road coloring (2011)
  9. Steinberg, Benjamin: Černý’s conjecture and group representation theory (2010)
  10. Trahtman, Avraham N.: A partially synchronizing coloring (2010)
  11. Almeida, Jorge; Steinberg, Benjamin: Matrix mortality and the Černý-Pin conjecture (2009)
  12. Roman, Adam: Synchronizing finite automata with short reset words (2009)
  13. Talhi, Chamseddine; Tawbi, Nadia; Debbabi, Mourad: Execution monitoring enforcement under memory-limitation constraints (2008)
  14. Trahtman, A. N.: An efficient algorithm finds noticeable trends and examples concerning the Černy conjecture (2006)
  15. Trahtman, A. N.: Reducing the time complexity of testing for local threshold testability (2004)
  16. Champarnaud, Jean-Marc (ed.); Maurel, Denis (ed.): Implementation and application of automata. 7th international conference, CIAA 2002, Tours, France, July 3--5, 2002. Revised papers (2003)
  17. Trahtman, A. N.: A package TESTAS for checking some kinds of testability (2003)
  18. Trakhtman, Avraham: Reducing the time complexity of testing for local threshold testability (2003)