2013-05-15

Practice Final #6 .

'''Originally Posted By: chris.ellis'''

Prove ALBA is decidable. Show all necessary lemmas. Lemma: Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly qng^n distinct configurations of M for a tape of length n. Algorithm that decides ALBA is as follows: On input , where M is an LBA and w is a string: 1. Simulate M on w for qng^n steps or until halts. 2. if M has halted, accept if it accepted and reject if rejected. If it has not halted, reject. Essentially, because an LBA will always have a finite number of configurations (qng^n), and because of the nature of the algorithm, it will always either accept or reject if halted after the qng^n number of steps. If it does not halt it will still reject and therefore is decidable Hun Wie David Do Christopher Ellis Steven Bui

'''Originally Posted By: chris.ellis''' 6. Prove ALBA is decidable. Show all necessary lemmas. Lemma: Let M be an LBA with q states and g symbols in the tape alphabet. There are exactly qng^n distinct configurations of M for a tape of length n. Algorithm that decides ALBA is as follows: On input , where M is an LBA and w is a string: 1. Simulate M on w for qng^n steps or until halts. 2. if M has halted, accept if it accepted and reject if rejected. If it has not halted, reject. Essentially, because an LBA will always have a finite number of configurations (qng^n), and because of the nature of the algorithm, it will always either accept or reject if halted after the qng^n number of steps. If it does not halt it will still reject and therefore is decidable Hun Wie David Do Christopher Ellis Steven Bui

Query Statistics

https://yioop.com/thread/3895

Total Elapsed Time for Queries: 0.04063200950622559 seconds.

SELECT LOCALE_NAME, WRITING_MODE FROM LOCALE WHERE LOCALE_TAG ='en-US'

Time: 0.0002081394195556641 seconds.

SELECT COALESCE(MAX(UPDATE_TIMESTAMP), 0) AS MOST_RECENT FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID = 2 AND ITEM_TYPE = 3 AND ITEM_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = 2 AND STATUS = 1) AND UPDATE_PERIOD = -4

Time: 0.0003569126129150391 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 3895 [2] => 1 )

Time: 0.003531932830810547 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 3895 [2] => 1 [3] => 1789988499 )

Time: 0.002141952514648438 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 3895 [2] => 1 )

Time: 8.511543273925781E-5 seconds.

DELETE FROM ITEM_IMPRESSION_SUMMARY WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -4
Array ( [0] => 2 [1] => 254 [2] => 3 )

Time: 0.002030849456787109 seconds.

INSERT INTO ITEM_IMPRESSION_SUMMARY VALUES (?, ?, ?, -4, ?, 0, -1, -1) ON CONFLICT DO NOTHING
Array ( [0] => 2 [1] => 254 [2] => 3 [3] => 1789988499 )

Time: 0.002219915390014648 seconds.

UPDATE ITEM_IMPRESSION_SUMMARY SET NUM_VIEWS = NUM_VIEWS + 1 WHERE USER_ID=? AND ITEM_ID=? AND ITEM_TYPE=? AND UPDATE_PERIOD = -2 AND UPDATE_TIMESTAMP = 0
Array ( [0] => 2 [1] => 254 [2] => 3 )

Time: 7.605552673339844E-5 seconds.

SELECT COUNT(GI.ID) AS NUM FROM GROUP_ITEM GI WHERE GI.GROUP_ID IN (SELECT GROUP_ID FROM USER_GROUP WHERE USER_ID = ? AND STATUS = 1) AND GI.TITLE NOT LIKE ? AND GI.PUBDATE > ?
Array ( [0] => 2 [1] => %2% [2] => 1789988477 )

Time: 0.0003728866577148438 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-4 )

Time: 0.0002129077911376953 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-37 )

Time: 6.008148193359375E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-202 )

Time: 5.412101745605469E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-687 )

Time: 5.197525024414062E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1115 )

Time: 4.982948303222656E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1138 )

Time: 5.102157592773438E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1140 )

Time: 3.218650817871094E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1149 )

Time: 3.290176391601562E-5 seconds.

SELECT PARENT_ID FROM GROUP_ITEM WHERE GROUP_ID=? AND USER_ID=? AND TITLE=? LIMIT 1
Array ( [0] => -1 [1] => 2 [2] => 2-1152 )

Time: 3.194808959960938E-5 seconds.

SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3895 )

Time: 0.0001020431518554688 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 254 )

Time: 4.696846008300781E-5 seconds.

SELECT COUNT(DISTINCT GI.ID) AS NUM FROM GROUP_ITEM GI, SOCIAL_GROUPS G, USER_GROUP UG, USERS O WHERE GI.PARENT_ID='3895' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.USER_ID=O.USER_ID AND GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND (( G.MEMBER_ACCESS IN ('2','3','4', '5')) OR (G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1'))

Time: 0.0005829334259033203 seconds.

SELECT DISTINCT GI.ID AS ID, GI.PARENT_ID AS PARENT_ID, GI.GROUP_ID AS GROUP_ID, GI.TITLE AS TITLE, GI.DESCRIPTION AS DESCRIPTION, GI.FLAG AS FLAG, GI.PUBDATE AS PUBDATE, GI.EDIT_DATE AS EDIT_DATE, G.OWNER_ID AS OWNER_ID, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.GROUP_NAME AS GROUP_NAME, P.USER_NAME AS USER_NAME, P.USER_ID AS USER_ID, GI.TYPE AS TYPE, GI.UPS AS UPS, GI.DOWNS AS DOWNS, G.VOTE_ACCESS AS VOTE_ACCESS FROM GROUP_ITEM GI, SOCIAL_GROUPS G, USER_GROUP UG, USERS P WHERE GI.PARENT_ID='3895' AND NOT LOWER(group_name) LIKE LOWER('Personal$%') AND (UG.USER_ID='2' OR G.REGISTER_TYPE IN ('4','3') ) AND GI.GROUP_ID=G.GROUP_ID AND GI.GROUP_ID=UG.GROUP_ID AND (( G.MEMBER_ACCESS IN ('2','3','4', '5')) OR (G.OWNER_ID = UG.USER_ID OR UG.USER_ID = '1')) AND GI.PARENT_ID NOT IN (SELECT DISCUSS_THREAD FROM GROUP_PAGE WHERE TITLE LIKE '%$$%' AND DISCUSS_THREAD IS NOT NULL) AND P.USER_ID = GI.USER_ID ORDER BY GI.PUBDATE ASC LIMIT 10 OFFSET 0

Time: 0.02576994895935059 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 254 )

Time: 0.0001680850982666016 seconds.

SELECT * FROM GROUP_ITEM WHERE ID=? LIMIT 1
Array ( [0] => 3895 )

Time: 0.0002188682556152344 seconds.

SELECT OPTIONS FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 254 )

Time: 4.816055297851562E-5 seconds.

SELECT STATUS FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )

Time: 0.0003061294555664062 seconds.

SELECT USER_NAME FROM USERS WHERE USER_ID = ?
Array ( [0] => 2 )

Time: 0.0001270771026611328 seconds.

SELECT * FROM VISITOR WHERE ADDRESS = :address AND PAGE_NAME = :page_name LIMIT 1
Array ( [:address] => 216.73.216.124 [:page_name] => forbidden_time_out )

Time: 0.0002839565277099609 seconds.

SELECT COUNT(DISTINCT G.GROUP_ID) AS NUM FROM USER_GROUP UG, SOCIAL_GROUPS G WHERE UG.USER_ID = ? AND UG.GROUP_ID = G.GROUP_ID AND ( UG.STATUS = 1 OR UG.STATUS = 5)
Array ( [0] => 2 )

Time: 0.0003540515899658203 seconds.

SELECT G.GROUP_ID AS GROUP_ID FROM SOCIAL_GROUPS G WHERE G.GROUP_NAME = ?
Array ( [0] => Personal$2 )

Time: 0.0001690387725830078 seconds.

SELECT USER_ID FROM USER_GROUP WHERE GROUP_ID = ?
Array ( [0] => -1 )

Time: 6.508827209472656E-5 seconds.

SELECT G.GROUP_ID AS GROUP_ID, G.GROUP_NAME AS GROUP_NAME, G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE, UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME, UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS, G.RENDER_ENGINE AS RENDER_ENGINE, G.GROUP_THEME AS GROUP_THEME, G.PAGE_HEADER AS PAGE_HEADER, G.PAGE_FOOTER AS PAGE_FOOTER FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 254 [:user_id] => 2 )

Time: 0.0002279281616210938 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => -2 )

Time: 0.0001440048217773438 seconds.

SELECT RENDER_ENGINE FROM SOCIAL_GROUPS WHERE GROUP_ID = ?
Array ( [0] => 254 )

Time: 3.099441528320312E-5 seconds.

SELECT G.GROUP_ID AS GROUP_ID, G.GROUP_NAME AS GROUP_NAME, G.OWNER_ID AS OWNER_ID, O.USER_NAME AS OWNER, REGISTER_TYPE, UG.STATUS AS STATUS, G.MEMBER_ACCESS AS MEMBER_ACCESS, G.VOTE_ACCESS AS VOTE_ACCESS, G.POST_LIFETIME AS POST_LIFETIME, UG.JOIN_DATE AS JOIN_DATE, G.OPTIONS AS OPTIONS, G.RENDER_ENGINE AS RENDER_ENGINE, G.GROUP_THEME AS GROUP_THEME, G.PAGE_HEADER AS PAGE_HEADER, G.PAGE_FOOTER AS PAGE_FOOTER FROM SOCIAL_GROUPS G, USERS O, USER_GROUP UG WHERE (UG.USER_ID = :user_id OR G.REGISTER_TYPE IN (3,4)) AND UG.GROUP_ID= :group_id AND UG.GROUP_ID=G.GROUP_ID AND OWNER_ID = O.USER_ID LIMIT 1
Array ( [:group_id] => 254 [:user_id] => 2 )

Time: 0.0002980232238769531 seconds.

SELECT STATUS FROM USER_GROUP WHERE USER_ID=? AND GROUP_ID=? LIMIT 1
Array ( [0] => 2 [1] => 254 )

Time: 8.797645568847656E-5 seconds.