FAdo.codes¶
Code theory module
New in version 1.0.
- class CodeProperty(name, alph)[source]¶
- See: K. Dudzinski and s. Konstantinidis: Formal descriptions of code properties: decidability, complexity,
implementation. International Journal of Foundations of Computer Science 23:1 (2012), 67–85.
- Variables:
Sigma – the alphabet
- class ErrCorrectProp(t)[source]¶
Error Correcting Property
Constructor :param SFT aut: Input preserving transducer
- class FixedProp(name, alph)[source]¶
Abstract class for fixed properties
- class IATProp(aut, name=None)[source]¶
Input Altering Transducer Property
Constructor :param SFT aut: Input preserving transducer
- class IPTProp(aut, name=None)[source]¶
Input Preserving Transducer Property
Constructor :param SFT aut: Input preserving transducer
- addToCode(aut, N, n=2000)[source]¶
Returns an NFA and a list W of up to N words of length ell, such that the NFA accepts L(aut) union W, which is an error-detecting language. ell is computed from aut
- makeCode(N, ell, s, n=2000, ov_free=False)[source]¶
Returns an NFA and a list W of up to N words of length ell, such that the NFA accepts W, which is an error-detecting language. The alphabet to use is {0,1,…,s-1}. where s <= 10.
- makeCodeO(N, ell, s, n=2000, end=None, ov_free=False)[source]¶
Returns an NFA and a list W of up to N words of length ell, such that the NFA accepts W, which is an error-detecting language. The alphabet to use is {0,1,…,s-1}. where s <= 10.
- Parameters:
- Returns:
an automaton and a list of strings
- Return type:
Note: not ov_free and end defined simultaneously Note: end should be a Word
- notMaxStatW(aut, ell, n=2000, ov_free=False)[source]¶
Returns a word of length ell to add into aut or None; simpler version of function nonMaxStatFEpsW
- class UDCodeProp(alphabet)[source]¶
Uniquely decodable Code Property
- maximalP(aut, U=None)[source]¶
Tests if the language is maximal w.r.t. the property :param DFA|NFA aut: the automaton :param DFA|NFA U: Universe of permitted words (sigma^* as default) :rtype: bool
- buildErrorCorrectPropF(fname)[source]¶
Builds an Error Correcting Property
- Parameters:
fname (str) – file name
- Return type:
- buildErrorCorrectPropS(s)[source]¶
Builds an Error Correcting Property from string
- Parameters:
s (str) – transducer string
- Return type:
- buildErrorDetectPropF(fname)[source]¶
Builds an Error Detecting Property
- Parameters:
fname (str) – file name
- Return type:
ErrDetectProp
- buildErrorDetectPropS(s)[source]¶
Builds an Error Detecting Property from string
- Parameters:
s (str) – transducer string
- Return type:
ErrDetectProp
- buildHypercodeProperty(alphabet)[source]¶
Builds a Hypercode Property
- Parameters:
alphabet (set) – alphabet
- Return type:
- buildInfixProperty(alphabet)[source]¶
Builds a Suffix Code Property
- Parameters:
alphabet (set) – alphabet
- Return type:
- buildOutfixProperty(alphabet)[source]¶
Builds a Outfix Code Property
- Parameters:
alphabet (set) – alphabet
- Return type:
- buildPrefixProperty(alphabet)[source]¶
Builds a Prefix Code Property
- Parameters:
alphabet (set) – alphabet
- Return type:
- buildSuffixProperty(alphabet)[source]¶
Builds a Suffix Code Property
- Parameters:
alphabet (set) – alphabet
- Return type:
- buildUDCodeProperty(alphabet)[source]¶
Builds a UDCodeProp (from thin air ;-)
- Parameters:
alphabet (set) – alphabet
- Return type:
- constructCode(n, l, p, ipt=False, seed=None)[source]¶
- Returns up to n words of length l satisfying the property p, the first one being seed.
If ipt is True, the property is assumed to be input-preserving transducer type
- Return type:
- editDistanceW(auto)[source]¶
Compute the edit distance of a given regular language accepted by the NFA via Input-altering transducer.
- Parameters:
auto (NFA) – language recogniser
- Returns:
The edit distance of the given regular language plus a witness pair
- Return type:
Attention
language should have at least two words
See also
Lila Kari, Stavros Konstantinidis, Steffen Kopecki, Meng Yang. An efficient algorithm for computing the edit distance of a regular language via input-altering transducers. arXiv:1406.1041 [cs.FL]
- exponentialDensityP(aut)[source]¶
- Checks if language density is exponential
Using breadth first search (BFS)
Attention
aut should not have Epsilon transitions
- fixedHierSubset(x, y)[source]¶
Returns whether x==y, or the fixed property with name x is a subset of y Currently (Jan 2015) the fixed properties names are ‘UD_codes’, ‘Prefix_codes’, ‘Suffix_codes’, ‘Infix_codes’, ‘Outfix_codes’, ‘Hypercodes’
- isSubclass(p1, p2)[source]¶
- Which property (language class) is a subclass of the other (if any).
It returns 1 if p1 is a subclass of p2; 2 if p2 is a subclass of p1; 3 if they are equal; 0 otherwise
- long2base(n, q)[source]¶
Maps n to a list of digits corresponding to the base q representation of n in reverse order
- notUniversalStatW(a, l, maxIter=20000)[source]¶
Tests statistically whether the NFA a is l-non-universal, by evaluating a on <= maxIter randomly chosen words of length l
- symmAndRefl(t, ipt=False)[source]¶
- Return the transducer t | t.inverse, if ipt is True;
return the transducer t | t.inverse | id, otherwise
- Return type: