Natural-class preserving structures

Nick Danis / nsdanis@wustl.edu / www.nickdanis.com

Supplemental material for Natural class-preserving transductions among phonological representations, presented at the Workshop on Model-Theoretic Representations in Phonology at Stony Brook University, September 22-24, 2022.

from itertools import chain, combinations

# from https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def get_shared_structure(segs, theory):
    '''
    find the shared vertices and edges between the structures in a theory
    '''
    structures = []
    for seg in segs:
        structures.append(theory[seg])
    return set.intersection(*structures)

def add_verteces(theory):
    '''
    programmatically add the vertex set to each representation
    based on the edges present
    '''
    for seg in theory.keys():
        verteces = set()
        for edge in theory[seg]:
            for v in edge:
                verteces.add(v)
        theory[seg].update(verteces)
    #return theory

def generate_extensions(theory):
    '''from the segments in the theory, generate the powerset
    (with singletons removed)'''
    natural_classes = powerset(theory.keys())
    return [nat for nat in natural_classes if len(nat) > 1]

def generate_shared_structure(theory):
    add_verteces(theory)
    shared = dict()
    for nat in generate_extensions(theory):
        nat_struct = get_shared_structure(nat,theory)
        if len(nat_struct) > 0:
            shared[nat] = nat_struct
    return shared
        
def generate_nce(theory):
    nce = dict()
    shared = generate_shared_structure(theory)
    for nat in shared:
        # get the segments not included in this class
        rest = set(theory.keys()) - set(nat)
        # initialize a list of potentially missing segments
        missing = []
        #print(nat, rest)
        # iterate through the rest
        for seg in rest:
            #print(f"current common structure is {yip_nce[nat]}")
            if shared[nat].issubset(theory[seg]):
                missing.append(seg)
        if len(missing) == 0:
            nce[tuple(sorted(list(nat)))] = shared[nat]
    return nce


def compare_theories(theory1, theory2, verbose=False):
    nce1 = generate_nce(theory1)
    nce2 = generate_nce(theory2)
    print(f"Natural classes unique to theory 1:")
    unique1 = nce1.keys() - nce2.keys()
    for nce in unique1:
        if verbose:
            print(f"{nce}\n\t{nce1[nce]}")
        else:
            print(f"{nce}")
    print(f"Natural classes unique to theory 2:")
    unique2 = nce2.keys() - nce1.keys()
    for nce in unique2:
        if verbose:
            print(f"{nce}\n\t{nce2[nce]}")
        else:
            print(f"{nce}")
    print("Natural classes in common:")
    common = nce2.keys() & nce1.keys()
    for nce in common:
        if verbose:
            print(f"{nce}\nT1:\t{nce1[nce]}\nT2:\t{nce2[nce]}")
        else:
            print(f"{nce}")

Oakden 2021

yip = {
    'L' : {('s','-u'), ('-u','l')},
    'H' : {('s','+u'), ('+u','h')},
    'M1' : {('s','-u'), ('-u','h')},
    'M2' : {('s','+u'), ('+u','l')},
    'HM' : {('s','+u'), ('+u','h'), ('+u','l')},
    'MH' : {('s','+u'), ('+u','l'), ('+u','h')},
    'ML' : {('s','-u'), ('-u','l'), ('-u','h')},
    'LM' : {('s','-u'), ('-u','l'), ('-u','h')}
}

bao = {
    'L' : {('s','T'), ('T','-u'), ('T','c'), ('c','l')},
    'H' : {('s','T'), ('T','+u'), ('T','c'), ('c','h')},
    'M1' : {('s','T'), ('T','-u'), ('T','c'), ('c','h')},
    'M2' : {('s','T'), ('T','+u'), ('T','c'), ('c','l')},
    'HM' : {('s','T'), ('T','+u'), ('T','c'), ('c','h'), ('c','l')},
    'MH' : {('s','T'), ('T','+u'), ('T','c'), ('c','h'), ('c','l')},
    'ML' : {('s','T'), ('T','-u'), ('T','c'), ('c','h'), ('c','l')},
    'LM' : {('s','T'), ('T','-u'), ('T','c'), ('c','h'), ('c','l')},
}

compare_theories(yip, bao)

Natural classes unique to theory 1:
Natural classes unique to theory 2:
Natural classes in common:
('HM', 'MH')
('H', 'HM', 'L', 'LM', 'M1', 'M2', 'MH', 'ML')
('LM', 'M1', 'ML')
('HM', 'LM', 'MH', 'ML')
('H', 'HM', 'M2', 'MH')
('H', 'HM', 'MH')
('HM', 'M2', 'MH')
('L', 'LM', 'M1', 'ML')
('H', 'HM', 'LM', 'M1', 'MH', 'ML')
('HM', 'L', 'LM', 'M2', 'MH', 'ML')
('L', 'LM', 'ML')
('LM', 'ML')

4-segment version

unified = {
    'p' : {('rt','Cpl'), ('Cpl','lab')},
    't' : {('rt','Cpl'), ('Cpl','cor')},
    'u' : {('rt','Vpl'), ('Vpl','lab')},
    'pw' : {('rt','Cpl'), ('Cpl','lab'), ('rt','Vpl'), ('Vpl','lab')},
    
}

v_features = {
    'p' : {('rt','Pl'), ('Pl','lab'), ('rt','-rnd')},
    't' : {('rt','Pl'), ('Pl','cor'), ('rt','-rnd')},
    'pw' : {('rt','Pl'), ('Pl','lab'), ('rt','+rnd')},
    'u' : {('rt','+rnd')},
}

compare_theories(unified, v_features)

Natural classes unique to theory 1:
('p', 'pw', 'u')
Natural classes unique to theory 2:
('p', 't')
Natural classes in common:
('p', 'pw')
('p', 'pw', 't', 'u')
('p', 'pw', 't')
('pw', 'u')

Full combinations

unified_d = {
    'p' : {('rt','Cpl'), ('Cpl','lab')},
    't' : {('rt','Cpl'), ('Cpl','cor')},
    'u' : {('rt','Vpl'), ('Vpl','lab')},
    'i' : {('rt','Vpl'), ('Vpl','cor')},
    'pw' : {('rt','Cpl'), ('Cpl','lab'), ('rt','Vpl'), ('Vpl','lab')},
    'tw' : {('rt','Cpl'), ('Cpl','cor'), ('rt','Vpl'), ('Vpl','lab')},
    'pj' : {('rt','Cpl'), ('Cpl','lab'), ('rt','Vpl'), ('Vpl','cor')},
    'tj' : {('rt','Cpl'), ('Cpl','cor'), ('rt','Vpl'), ('Vpl','cor')},
    
}

v_features_d = {
    'p' : {('rt','Pl'), ('Pl','lab'), ('rt','-rnd'), ('rt','-front')},
    't' : {('rt','Pl'), ('Pl','cor'), ('rt','-rnd'), ('rt','-front')},
    'u' : {('rt','+rnd'), ('rt','-front')},
    'i' : {('rt','-rnd'), ('rt','+front')},
    'pw' : {('rt','Pl'), ('Pl','lab'), ('rt','+rnd'), ('rt','-front')},
    'tw' : {('rt','Pl'), ('Pl','cor'), ('rt','+rnd'), ('rt','-front')},
    'pj' : {('rt','Pl'), ('Pl','lab'), ('rt','-rnd'), ('rt','+front')},
    'tj' : {('rt','Pl'), ('Pl','cor'), ('rt','-rnd'), ('rt','+front')},

}

compare_theories(unified, v_features)

Natural classes unique to theory 1:
('p', 'pw', 'u')
Natural classes unique to theory 2:
('p', 't')
Natural classes in common:
('p', 'pw')
('p', 'pw', 't', 'u')
('p', 'pw', 't')
('pw', 'u')

Three places, with double articulations

unified_e = {
    'p' : {('rt','Cpl'), ('Cpl','lab')},
    't' : {('rt','Cpl'), ('Cpl','cor')},
    'k' : {('rt','Cpl'), ('Cpl','dors')},
    'u' : {('rt','Vpl'), ('Vpl','lab')},
    'i' : {('rt','Vpl'), ('Vpl','cor')},
    'pw' : {('rt','Cpl'), ('Cpl','lab'), ('rt','Vpl'), ('Vpl','lab')},
    'tw' : {('rt','Cpl'), ('Cpl','cor'), ('rt','Vpl'), ('Vpl','lab')},
    'kw' : {('rt','Cpl'), ('Cpl','dors'), ('rt','Vpl'), ('Vpl','lab')},
    'pj' : {('rt','Cpl'), ('Cpl','lab'), ('rt','Vpl'), ('Vpl','cor')},
    'tj' : {('rt','Cpl'), ('Cpl','cor'), ('rt','Vpl'), ('Vpl','cor')},
    'kj' : {('rt','Cpl'), ('Cpl','dors'), ('rt','Vpl'), ('Vpl','cor')},
    'kp' : {('rt','Cpl'), ('Cpl','dors'), ('Vpl','lab')},
    'tp' : {('rt','Cpl'), ('Cpl','cor'), ('Vpl','lab')},
    
}

v_features_e = {
    'p' : {('rt','Pl'), ('Pl','lab'), ('rt','-rnd'), ('rt','-front')},
    't' : {('rt','Pl'), ('Pl','cor'), ('rt','-rnd'), ('rt','-front')},
    'k' : {('rt','Pl'), ('Pl','dors'), ('rt','-rnd'), ('rt','-front')},
    'u' : {('rt','+rnd'), ('rt','-front')},
    'i' : {('rt','-rnd'), ('rt','+front')},
    'pw' : {('rt','Pl'), ('Pl','lab'), ('rt','+rnd'), ('rt','-front')},
    'tw' : {('rt','Pl'), ('Pl','cor'), ('rt','+rnd'), ('rt','-front')},
    'tw' : {('rt','Pl'), ('Pl','dors'), ('rt','+rnd'), ('rt','-front')},
    'pj' : {('rt','Pl'), ('Pl','lab'), ('rt','-rnd'), ('rt','+front')},
    'tj' : {('rt','Pl'), ('Pl','cor'), ('rt','-rnd'), ('rt','+front')},
    'kj' : {('rt','Pl'), ('Pl','dors'), ('rt','-rnd'), ('rt','+front')},
    'kp' : {('rt','Pl'), ('Pl','dors'), ('Pl','lab'), ('rt','-rnd'), ('rt','-front')},
    'tp' : {('rt','Pl'), ('Pl','dors'), ('Pl','cor'), ('rt','-rnd'), ('rt','-front')},

}

compare_theories(unified_e, v_features_e)

Natural classes unique to theory 1:
('kj', 'pj', 'tj', 'tw')
('i', 'k', 'kj', 'kp', 'kw', 'p', 'pj', 'pw', 't', 'tj', 'tp', 'tw', 'u')
('kw', 'pj', 'pw', 'tw', 'u')
('kp', 'kw')
('p', 'pj', 'pw')
('kj', 'kw', 'pj', 'pw', 'tj', 'tw')
('i', 'kj', 'pj', 't', 'tj', 'tp', 'tw')
('pj', 'tw')
('i', 'kj', 'kp', 'kw', 'pj', 'pw', 'tj', 'tp', 'tw', 'u')
('pj', 'pw')
('tj', 'tw')
('pj', 'tp', 'tw')
('i', 'kj', 'kw', 'pj', 'pw', 'tj', 'tw', 'u')
('k', 'kj', 'kp', 'kw')
('kp', 'kw', 'pw', 'tp', 'tw')
('kj', 'kw')
('kp', 'kw', 'pj', 'pw', 'tp', 'tw')
('kw', 'pw', 'tw')
('tj', 'tp', 'tw')
('kw', 'pj', 'pw', 'tw')
('kj', 'pj', 't', 'tj', 'tp', 'tw')
('kj', 'pj', 'tj', 'tp', 'tw')
('tp', 'tw')
('kj', 'kp', 'kw', 'pj', 'pw', 'tj', 'tp', 'tw')
('kj', 'kp', 'kw')
('kp', 'kw', 'pw', 'tp', 'tw', 'u')
('k', 'kj', 'kp', 'kw', 'p', 'pj', 'pw', 't', 'tj', 'tp', 'tw')
('kp', 'kw', 'pj', 'pw', 'tp', 'tw', 'u')
('kw', 'pw', 'tw', 'u')
('kp', 'kw', 'p', 'pj', 'pw', 'tp', 'tw', 'u')
('kp', 'kw', 'p', 'pj', 'pw', 'tp', 'tw')
('i', 'kj', 'pj', 'tj', 'tp', 'tw')
('i', 'kj', 'pj', 'tj', 'tw')
('t', 'tj', 'tp', 'tw')
Natural classes unique to theory 2:
('i', 'k', 'kj', 'kp', 'p', 'pj', 't', 'tj', 'tp')
('k', 'kp', 'p', 't', 'tp')
('k', 'kj', 'kp', 'tp', 'tw')
('k', 'kj', 'kp', 'p', 'pj', 't', 'tj', 'tp')
('kp', 'p', 'pw')
('k', 'kp', 'p', 'pw', 't', 'tp', 'tw')
('i', 'k', 'kj', 'kp', 'p', 'pj', 'pw', 't', 'tj', 'tp', 'tw', 'u')
('kp', 'p')
('k', 'kj', 'kp', 'p', 'pj', 'pw', 't', 'tj', 'tp', 'tw')
('kp', 'p', 'pj')
('kp', 'p', 'pj', 'pw')
('k', 'kp', 'tp', 'tw')
('t', 'tp')
('k', 'kj', 'kp', 'tp')
('k', 'kp', 'tp')
('pw', 'tw')
('pw', 'tw', 'u')
('t', 'tj', 'tp')
('k', 'kp', 'p', 'pw', 't', 'tp', 'tw', 'u')
Natural classes in common:
('i', 'kj', 'pj', 'tj')
('kj', 'pj', 'tj')