set,equality,coq , Making and comparing Sets in Coq


Making and comparing Sets in Coq

Question:

Tag: set,equality,coq

I'm having trouble understanding whether it is possible to prove that two sets (in this case regular languages) are identical and thus interchangeable. From what I understand, sets can be equivalent even if they are not constructively equal.

Regular languages are sets of strings, but I don't see how to say that r1 = r2 so that something like symmetry can be used in a proof.

Here is my RegularLanguage declaration:

Inductive RegularLanguage (A : Set) : Set :=
  | EmptyLang : RegularLanguage A
  | EmptyStr : RegularLanguage A
  | Unit : A -> RegularLanguage A
  | Union :
    RegularLanguage A
    -> RegularLanguage A
    -> RegularLanguage A
  | Concat :
    RegularLanguage A
    -> RegularLanguage A
    -> RegularLanguage A
  | KleeneStar : RegularLanguage A -> RegularLanguage A
.

Even though I say the type is Set, this doesn't create a set of strings, as far as I can see. Do I need some function of type RegularLanguage -> Set of strings?

Thank you for the help.


Answer:

There are a few misunderstandings about some Coq concepts which I'll try to clarify.

First, in Coq, you shouldn't view Set as what we call "set" in traditional mathematics. Instead, you should view it as a type. Coq also has Type, but for the purposes of this post you can view both Set and Type as being interchangeable. To avoid confusion, from now on, I will use "set" to refer to the usual concept of set in traditional mathematics, and "type" to refer to elements of Set and Type in Coq.

So, what exactly is the difference between a set and a type? Well, in normal mathematics, it makes sense to ask oneself whether anything is a member of any given set. Thus, if we were to develop the theory of regular expressions in normal mathematics, and each regular expression were seen as a set, it would make sense to ask questions such as 0 \in EmptyLang, because, even though 0 is a natural number, it could be the element of any set a priori. As a less contrived example, the empty string is both a member of the full language (i.e. the one that contains all strings) and of the Kleene closure of any base language.

In Coq, on the other hand, each valid element of the language has exactly one type. The empty string, for instance, has type list A for some A, which is written [] : list A. If we try to ask whether [] belongs to some regular language using the "has type" syntax, we get an error; try typing e.g.

Check ([] : EmptyLang). 

Both sets and types can be seen as collections of elements, but types are in a sense more restrictive: for instance, one can take the intersection of two sets, but there's no way of taking the intersection of two types.

Second, when you write

Inductive RegularLanguage (A : Set) : Set := (* ... *)

this does not mean that the elements that you list below the header define sets nor types. What this means is that, for each type A (the (A : Set) part), you are defining a new type noted RegularLanguage A (the RegularLanguage (A : Set) : Set part), whose elements are freely generated by the list of constructors given. Thus, we have

EmptyLang : RegularLanguage nat

RegularLanguage nat : Set

but we don't have

EmptyLang : Set

(once again, you can try typing all the above judgments into Coq to see which are accepted and which aren't).

Being "freely generated" means, in particular, that the constructors you listed are injective and disjoint. As larsr noted previously, in particular, it is not the case that Union l1 l2 = Union l2 l1; as a matter of fact, you will usually be able to prove Union l1 l2 <> Union l2 l1. The problem is that there is a mismatch between the notion of equality that you get for inductively defined types in Coq (which you can't change) and your intended notion of equality for regular languages.

While there are a few ways around this, I think the easiest one is to use the setoid rewrite feature. This would involve first defining a function or predicate (e.g., as larsr suggested, a boolean function regexp_match : RegularLanguage A -> list A -> bool) to determine when a regular language contains some string. You can then define an equivalence relation on languages:

Definition regexp_equiv A (l1 l2 : RegularLanguage A) : Prop :=
  forall s, regexp_match l1 s = regexp_match l2 s.

and use setoid rewrite to rewrite with this equivalence relation. There is a small caveat, however, which is that you can only rewrite with an equivalence relation in contexts that are compatible with this equivalence relation, and you need to explicitly prove lemmas to do so. You can find more details in the reference manual.


Related:


Handling caching of very large set


java,file,memory,set
I have a Set of BigInteger that I want to cache. This Set can go up to ~100K size. The application i'm using is quite light : it does not have a lot of memory (heap about 256mb) and does not use a database (the team is considering it for...

Get unique values in List of Lists in python


python,list,set,unique
I want to create a list (or set) of all unique values appearing in a list of lists in python. I have something like this: aList=[['a','b'], ['a', 'b','c'], ['a']] and i would like the following: unique_values=['a','b','c'] I know that for a list of strings you can just use set(aList), but...

How to access class data in a set of pointers to that class


c++,set
I have a set of pointers: set<StudentInterface*, Comparator> studentSet; These pointers point to Student classes which inherit from StudentInterface and contain an int value ID. I want to test if a certain class has a particular value for ID. My current idea for doing so is as follows: if(studentSet.find(????->getID()) !=...

To check objects inside std::array has identical member data


c++,std,equality
Cards.h class Card { public: // Card suits struct Suit { // Suits in order enum Enum { Clubs, Diamonds, Hearts, Spades, }; }; // Card rank struct Rank { // Ranks with aces low enum Enum { Ace, Two, King, .... ... }; }; // constructors //get & set...

Haskell: `==' is not a (visible) method of class


haskell,compiler-errors,instance,equality,typeclass
So, when I compile the following piece of code edited: instance (Eq a) => PartOrd a where [] == [] = True (x:xs) == (y:ys) = x==y && xs==ys _==_ = False xs /= ys = not (xs == ys) I get: `==' is not a (visible) method of class...

Does __ne__ use an overridden __eq__?


python,comparison,equality
Suppose I have the following program: class A(object): def __eq__(self, other): return True a0 = A() a1 = A() print a0 != a1 If you run it with Python the output is True. My question is the __ne__ method is not implemented, does Python fall on a default one? if...

retrieve all the smallest strings from a set in python


python,string,list,set,min
I have a set which looks like set(['A', 'BF', 'B', 'BA', 'ABF', 'AF', 'F', 'BFA', 'AFB', 'BAF', 'FA', 'FB', 'AB', 'FAB', 'FBA']) and I'm trying to get all Strings which has the smallest length into a list I tried using print min((element for element in getParts(working_scheme,k)), key=len) which just prints...

Template C++: How to access iterator value for both std::map and std::set?


c++,templates,dictionary,stl,set
I have a specific search function. Because it's used on both std::set and std::map, it was duplicated in our code (not using template). I have to maintain those two functions, and I'd like to move them to a single function using a template (and then have only one search preocedure...

Looking for elements in a set


python,set
I'm a little confused on which data structure to use to compare if an element matches another element in a set. Lets say user_input asks the user to type in their name. if their name matches up they are granted access but this doesn't work. access = set(['John', 'Jane', 'Jack',...

Removing subsets in array of Sets


arrays,swift,set
Is there an efficient way to remove subsets from an array of sets E.g. array of arrays [[2, 3, 4, 7, 8, 9, 10], [1, 5, 6], [3, 7, 10], [4, 8, 9], [5, 6], [7, 10], [8, 9], [6], [9]] to output an array [[2, 3, 4, 7, 8,...

Printing off the content of Array or Set using for loop


arrays,swift,for-loop,set,println
When trying to print off the content of Set or Array using for loop I don't receive values but number of them. For example: var favouriteSports: Set = ["Snowboarding", "Skateboarding", "Surfing"] for genre in favouriteSports { print("\(genre)") } What I wanted to receive in console is "Snowboarding, Skateboarding, Surfing" but...

Why does the Java equals(Object O) method not have a variant which can take a specific object type (e.g. String, Integer, etc) as input?


java,generics,equality,string-comparison,method-signature
I come across problems where I need to compare two strings (or any other object ) for equality/non-equality using Java language. There are two methods on String Object very useful for this purpose viz. compareTo(Object O), which returns a integer result of comparison while other equals(Object o), which returns a...

How to check if a value is present in any of given sets


python,set
Say I have different sets (they have to be different, I cannot join them as per the kind of data I am working with): r = set([1,2,3]) s = set([4,5,6]) t = set([7,8,9]) What is the best way to check if a given variable is present in either of them?...

The union of several vectors


matlab,set
I have three vectors, v1, v2, and v3, each of which has 500 values. The three vectors may or may not have the same values. I want to know how to get the union set of the three vectors. If they have same values, the value can only be dislayed...

What is faster: equal check or sign check


java,performance,comparison,equality,cpu-architecture
I wonder which operation works faster: int c = version1.compareTo(version2); This one if (c == 1) or this if (c > 0) Does sign comparasion use just a one bit check and equality comparasion use substraction, or it is not true? For certainty, let's say we work on x86. P.S....

How to generate all partitions of a set


algorithm,set,combinatorics,backtracking
For a set of the form A = {1, 2, 3, ..., n}. It is called partition of the set A, a set of k<=n elements which respect the following theorems: a) the union of all the partitions of A is A b) the intersection of 2 partitions of A...

Unexpected behaviour in Python OrderedSet.issuperset()


python,set,set-theory
I have two OrderedSets and I'm trying to check whether one in a subset of the other - both the elements and their order is important. However, the orderedset package is giving me strange results. >>> import orderedset >>> a = orderedset.OrderedSet([433, 316, 259]) >>> b = orderedset.OrderedSet([433, 316, 69])...

Adding a sentence word by word into a set using Recursion


java,recursion,set
I am trying to add each word of a sentence into a set using recursion in java. Punctuation does not matter. My problem is that only the first word of the sentence is being printed after I print the list. For example the sentence "One Two Three Four" would come...

How to use set(data structure) in mongodb console?


javascript,set
As I understand, the mongodb console has an integrated javascript interpreter so my question is why this code does not work if its a valid javascript: //db = connect("localhost:27017/tecnicas") function getRandomInt(min, max) { return Math.floor(Math.random() * (max - min + 1)) + min; } diaFavorito = ["lunes", "martes", "miercoles", "sabado"]...

Java String Parser to find string, save it and print it


java,email,parsing,set
I wrote this little part down here to find tags in email subjects, extract them and save them to my Set. I.e. if email subject is "Hello there #bro #senpai" it should find and extract both 'bro' and 'senpai' and put it into m_aTags (which is just custom type Set...

What is the Pythonic way to iterate over set intersection and exclusions?


python,dictionary,set,iteration,set-intersection
set_of_A_key and set_of_B_keyare two set of keys of dictionary dict_A and dict_B. I want operate over the dictionary values for the keys in the following three sets: (set_of_A_key & set_of_B_key), (set_of_A_key - set_of_B_key) and (set_of_B_key - set_of_A_key) What is the pythonic way to do this? This one is elegant with...

MySQL Set without predefined values


mysql,sql,set
I want to have a MySQL column as a SET for multiple ID's, but I don't want to predefine all possible values. What I'm looking for is a MySQL datatype, which supports set-functionalities like IN in a MySQL query. It's only used for numeric entries....

How to override isEqual: for CLBeacon?


ios,objective-c,core-location,equality
Background I have a method, provided by a 3rd party library, that returns an array of CLBeacons. - (void)beaconManager:(ESTBeaconManager *)manager didRangeBeacons:(NSArray *)beacons inRegion:(CLBeaconRegion *)region This method is called at regular intervals and the array contains a list of the beacons that are in range. Objects in the array are not...

Generate all combinations of strings and their substrings in a set — python


python,string,set,combinations
I want to get all combinations of of strings from a set of strings. For Example: permut = set() permut.add("D") permut.add("C") def getAllKombos(stuff): returnvalue = set() for L in range(0, len(stuff) + 1): for subset in itertools.combinations(stuff, L): for i in subset: x = x + (str(i)) returnvalue.add(x) x =...

Scala Set different operations


scala,set,operation
So here is my code snippet: val check = collection.mutable.Set[String]() if (check.isEmpty) { println("There is no transfer data available yet, please use the 'load' command to initialize the application!") } val userSelection = scala.io.StdIn.readLine("Enter your command or type 'help' for more information:") val loadCommand = """^(?:load)\s+(.*)$""".r userSelection match { case...

How do nested variable types change time complexity?


python,list,dictionary,set,time-complexity
I'm creating a list with nested types like this: nested = [{}, set([]), []] Assume each item in 'nested' has many items in it. For each type of item in 'nested', what operations from Python's Wiki change complexity because the items are nested? For things like add, remove, pop, etc....

Using comparison function for the key type for sets results in runtime error


c++,c++11,set,runtime-error,decltype
I've read this question and it does not help me. My question is: Why am I getting a runtime error when using a comparison function for the key type for set as below? multiset<Phone, decltype(comp)*> phones { Phone(911), Phone(112) }; //^^^^^^^^^^^^^^^ In VC2013 it gives me this for the above...

Order-independant Hash Algorithm


java,algorithm,hash,set
I am currently working on a collection library for my custom programming language. I already have several data types (Collection, List, Map, Set) and implementations for them (mutable and immutable), but what I was missing so far was hashCode and equals. While these are no problem for Lists as they...

Bitwise and of subsets of an array


arrays,set,bit-manipulation,bitwise-operators
Can anyone give a hint how to approach this problem? Given an array A. Is there any subset of array A in which if we do AND of all elements of that subset then output should be in power of two. I've thought of generating a power-set and solving but...

Multidimensional List get Position of a String Python


python,string,list,indexing,set
I got following List relational_scheme = [["F",["DC"]],["A",["EBD"]],["DC" , ["BAF"]],["E",["DB"]]] Now i want to get the second List as a Set like def returnSetOfList(relational_scheme,"F") So that this output generates set(["DC"]) How can i make this? an easy Index don't work. Thanks in advance. UPDATE got it, was just blind Solution: def...

Longest substring with only 2 distinct chars in C++


c++,string,stl,set
I am trying to find the longest substring with at most 2 distinct characters. It is a brute force program which just uses all possible substrings and checks if they have 2 or more distinct chars. I use a set to keep track of the distinct chars. #include <iostream> #include...

Julia's dictionary method `haskey` returning false when key is present


dictionary,equality,julia-lang
I am new to Julia and I am not sure why the last line evaluates to false: type Point{T} x::T y::T end D = [Point(1.,2.) => 42] haskey(D, Point(1., 2.)) #False! Clearly the key exists so what's going on here!? Edit. If I don't use a class Point, it works...

Android List and Array set


android,arrays,list,set
I'm trying to save this info on a Service that is triggered by receiving a call but it's crashing after I use the .set SimpleDateFormat df = new SimpleDateFormat("HH:mm:ss dd-MM-yyyy", Locale.getDefault()); Calendar calendar = Calendar.getInstance(); String currentDateTimeString = df.format(calendar.getTime()); List<String> lastCall = new ArrayList<String>(); lastCall.set(0, currentDateTimeString); lastCall.add("12:22:12 12-03-2014"); lastCall.add("22:06:34 14-07-2013");...

How to group sets by similarity in contained elements


python,set,similarity
I am using Python 2.7. I have routes which are composed of arrays of nodes that connect to each other. The nodes are identified by a string key, but for ease I will use numbers: sample_route = [1,2,3,4,7] #obviously over-simplified; real things would be about 20-40 elements long I will...

Reversing logic of a product-country mapping


python,dictionary,set
I have a dictionary that maps the territory_code to what productIds are available: items = {'US': set(123, 948, 200), 'AG': set(132, 123), 'AZ': set(123)} I would like to reverse the mapping so it gives me the items and maps those to the territory. It should give me: {123: set('US', 'AZ',...

Set options for ZADD command in laravel redis


php,laravel,redis,set
I'm trying to set options for ZADD with laravel redis but am failing. The option I need to set is NX, as stated in the documentation: ZADD options (Redis 3.0.2 or greater) ZADD supports a list of options, specified after the name of the key and before the first score...

Learning Sets : How do I place the asterisks and ampersands on function arguments and function calls?


c,set,function-pointers,function-call
I am confused as to when to put * and & on function arguments and ampersands on function calls and especially confused on pointers. I would also like to do a dynamic allocation in initialize but is it allowed in sets? What I understand is that my set is only...

Using a text file as a set of values swift [duplicate]


ios,swift,set,text-files
This question is an exact duplicate of: Getting a set of values from resource file swift [closed] I'm working on a project that selects one or more words contains entered(user) keywords.That's why I'm using a set. But the set is turkish dictionary. That is to say, it contains 68k...

LinkedHashSet and subList, getting n of collection


java,math,set,linkedhashset
I am trying to do a homework in math which is find a subset of collection {1,2,..,n} where n is a number given in the code, I cannot get it done with the sublist so I need to get your help with a math programming. For example for n =...

Keep (minim) object in a collection by two attribute keys in java


java,collections,set,comparator,treeset
For example I have a list that contains 3 objects: List<Student> studentList= new ArrayList<Student>(); list.add(new Student("name1", 5); list.add(new Student("name3", 6); list.add(new Student("name1", 7); class Student{ String name; Integer grade;} My filtering logic: if name is equal then i need to filter out the objects that have maximum grade - so...

Set S of n numbers - have a subset with the probability of each element of S occuring in it equal


algorithm,set
I have this problem You are given a set S of n numbers. You must pick a subset S′ of k numbers from S such that the probability of each element of S occurring in S′ is equal (i.e., each is selected with probability k/n). You may make only one...

Comparing arrays, sets & their elements in SWIFT


ios,arrays,swift,multidimensional-array,set
I'm fairly new to coding in and I usually find answers already on here. However on this occasion I've been trying to find a method in swift that will allow me to identify pairs of numbers, in another array of unpaired numbers within another array for example in the image...

Python Convert set to list, keep getting TypeError: 'list' object is not callable


python,list,set
I am trying to write a program that adds items to a list based on a random number. Part of the program is potentially rolling additional items, but all duplicate items should be rerolled. My issue is that when I try to do this using the methods I was able...

Variable indexes outside of defined range in AMPL


variables,indexing,set,linear-programming,ampl
Not too familiar with AMPL, but running into some issues with indexes... Basically, I have some variables defined as such: var array{i in set}; And I need to do some amount of checking the elements around a given i in some of the constraints: subject to Constraint{i in set}: array[i]...

Scala set element uniqueness: What to implement for comparison of user defined classes?


scala,set,compare,unique
I am trying to find this information in the Scala documentation but it looks like it is not there. In the case of Java this was dependent of the Set implementation that was used, AFAIK. In some cases the method to implement was equals, in the case of a HashSet...

Element is present but `Set.contains(element)` returns false


java,hash,set,contains,hashset
How can an element not be contained in the original set but in its unmodified copy? The original set does not contain the element while its copy does. See image. The following method returns true, although it should always return false. The implementation of c and clusters is in both...

Removing duplicates from arraylist using set [duplicate]


java,arraylist,set
This question already has an answer here: Common elements in two lists 4 answers Have 2 sets with duplicates set1 ={1,2,3,4,5} set2 = {1,3,6,7} and the result should be set3 ={2,4,5,6,7} Please let me reiterate that I want to use Set interface and the result set should be ordered...

Joining (union) of Sets inside a Set in Java


iterator,set,java-7,java-api,set-union
I have a map where the values are sets of integers. What i'd want to do is to get in the best way possible (using only the Java API would be great) the union of all the sets of Integers. Map<Long, Set<Integer>> map; What I thought so far is to...

why “==” working differently for integer and strings reference? [duplicate]


java,equality
This question already has an answer here: How do I compare strings in Java? 23 answers May I know how == works here? public class App { public static void main(String[] args) { String s1 = new String("str"); String s2 = new String("str"); System.err.println("why it,s "+String.valueOf(s1==s2)); int i1 =...

Java How create a set of object with two classes?


java,object,set
I have a logical problem to understand, how create a private set of inhabitant object. Here my two classes: package main; import java.util.Set; /** * @author * @version 0.1 * */ public class City { private String name; /** *HERE is my Problem*/ private Set<Inhabitants> Inhabitants { } /** *...