TURING MACHINES HAVE BEEN STUDIED AS DYNAMICAL SYSTEMS FOR MORE THAN TWO DECADES, FIRST FORMALIZED BY KURKA, PROPOSING A TOPOLOGICAL DYNAMICAL SYSTEM NAMED TURING MACHINE WITH MOVING TAPE (TMT). IT WAS CONJECTURED THAT EVERY TMT HAS AT LEAST ONE PERIODIC POINT. NOWADAYS, THERE ARE SEVERAL EXAMPLES OF APERIODIC TURING MACHINES, DISPROVING KURKA?S CONJECTURE. MOREOVER, ONE OF THESE MACHINES, NAMED SMART, HAS OTHER INTERESTING PROPERTIES LIKE REVERSIBILITY, COMPLETENESS, APERIODICITY, TOPOLOGICAL MINIMALITY, AMONG OTHERS. THIS MACHINE HAS FOUR STATES AND WORKS OVER AN ALPHABET OF THREE SYMBOLS. IN THIS RESEARCH, WE STUDY THE DYNAMICAL PROPERTIES OF BINSMART, A 2-SYMBOLS RECONSTRUCTION OF THE MAIN DYNAMIC OF SMART MACHINE. THIS MACHINE RESULTS TO BE APERIODIC, TOPOLOGICALLY MINIMAL (THEREFORE TRANSITIVE) BUT NOT TIME-SYMMETRIC, AS IT IS NOT A DIRECT TRANSLATION OF THE ORIGINAL MACHINE. WE ALSO PROVE THAT ITS T-SHIFT IS A PRIMITIVE SUBSTITUTION.

A SIMPLE REVERSIBLE TURING MACHINE WITH FOUR STATES, THREE SYMBOLS AND NO HALTING CONFIGURATION IS CONSTRUCTED THAT HAS NO PERIODIC ORBIT, SIMPLIFYING A CONSTRUCTION BY BLONDEL, CASSAIGNE AND NICHITIU AND POSITIVELY ANSWERING A CONJECTURE BY KARI AND OLLINGER. THE CONSTRUCTED MACHINE HAS OTHER INTERESTING PROPERTIES: IT IS SYMMETRIC BOTH FOR SPACE AND TIME AND HAS A TOPOLOGICALLY MINIMAL ASSOCIATED DYNAMICAL SYSTEM WHOSE COLUMN SHIFT IS ASSOCIATED TO A SUBSTITUTION. USING A PARTICULAR EMBEDDING TECHNIQUE OF AN ARBITRARY REVERSIBLE TURING MACHINE INTO THE ONE PRESENTED, IT IS PROVEN THAT THE PROBLEM OF DETERMINING IF A GIVEN REVERSIBLE TURING MACHINE WITHOUT HALTING STATE HAS A PERIODIC ORBIT IS UNDECIDABLE.

TWO SETS A AND B , WHOSE ELEMENTS FULFILL A TOTAL ORDER ON OPERATOR ? , CAN HAVE A BINARY RELATION R?A×B REPRESENTED BY THE K 2 -TREE COMPACT DATA STRUCTURE, WHICH GREATLY IMPROVES STORAGE SPACE. CURRENTLY, COUNT QUERY IS MANAGED BY EITHER USING RANGE QUERY OR TO MODIFY THE STRUCTURE TO HAVE AGGREGATE INFORMATION, IMPLYING ADDITIONAL TIME OR SPACE IN ORDER TO PERFORM THE QUERY. THIS ARTICLE PRESENTS COMPACT COUNT , WHICH EXPLOITS THE K 2 -TREE PROPERTIES TO REDUCE THE PATHS TO BE SCANNED TO COUNT THE NUMBERS IN A RANGE R , THUS ENSURING AN EXPECTED RUNTIME OF O(LOGKRLOGKN) AND STORAGE OF O(LOGKR) WITH THE K 2 -TREE PARAMETERS N AND K . OUR ALGORITHM WAS COMPARED THROUGH A SERIES OF EXPERIMENTS THAT CONSIDER BOTH SYNTHETIC DATA WITH DIFFERENT DISTRIBUTIONS AND REAL DATA, WITH A SOLUTION BASED ON THE RANGE ALGORITHM. EXPERIMENTAL RESULTS SHOW THAT COMPACT COUNT IS 250 TO 1,000 TIMES FASTER THAN RANGE ON SYNTHETIC AND REAL DATA, RESPECTIVELY, WITH A SMALL ADDITIONAL STORAGE COST, AS EXPECTED BY THE THEORETICAL ANALYSIS.

IN THE CONTEXT OF BIG DATA SCENARIOS, THE PRESENCE OF EXTENSIVE STATIC DATASETS IS NOT UNCOMMON. TO FACILITATE EFFICIENT QUERIES ON SUCH DATASETS, THE UTILIZATION OF MULTIPLE INDEXES, SUCH AS THE KD-TREE, BECOMES IMPERATIVE. THE CURRENT SCALE OF MANAGED POINTS MAY, HOWEVER, EXCEED THE CAPACITY OF PRIMARY MEMORY, POSING A SIGNIFICANT CHALLENGE. IN THIS ARTICLE WE INTRODUCE CKD-TREE, A COMPACT DATA STRUCTURE DESIGNED TO REPRESENT A KD-TREE EFFICIENTLY. THE STRUCTURE CKD-TREE IS ESSENTIALLY AN ENCODING OF THE SPIRAL CODE SEQUENCE OF POINTS WITHIN AN IMPLICIT KD-TREE (IKD-TREE) USING DIRECTLY ADDRESSABLE CODES (DACS). THE UNIQUE FEATURE OF CKD-TREE LIES IN ITS ABILITY TO PERFORM SPIRAL ENCODING AND DECODING OF POINTS BY RELYING SOLELY ON KNOWLEDGE OF THEIR PARENT POINTS WITHIN THE IKD-TREE. THIS INHERENT PROPERTY, COMBINED WITH DACS? DIRECT ACCESS CAPABILITY TO SEQUENCE ELEMENTS, ENABLES CKD-TREE TO TRAVERSE AND EXPLORE THE TREE WHILE DECODING ONLY THE NODES RELEVANT TO QUERIES. THE ARTICLE DETAILS THE ALGORITHMS NECESSARY FOR CREATING AND MANIPULATING A CKD-TREE, AS WELL AS ALGORITHMS FOR EVALUATING TWO FUNDAMENTAL QUERIES OVER POINTS: THE POINT QUERY AND THE RANGE QUERY . TO ASSESS THE PERFORMANCE OF CKD-TREE, A SERIES OF EXPERIMENTS ARE CONDUCTED, COMPARING IT WITH IKD-TREE AND K 2 -TREE DATA STRUCTURES. THE EVALUATION METRICS INCLUDE COMPRESSION EFFICIENCY AND EXECUTION TIME OF QUERIES. CKD-TREE ACHIEVES A COMPRESSION RATIO COMPARABLE TO THAT OF K 2 -TREE, APPROXIMATELY 70%, DEMONSTRATING HEIGHTENED EFFICIENCY, PARTICULARLY IN SCENARIOS CHARACTERIZED BY SPARSE DATA. ADDITIONALLY, CONSISTENT WITH EXPECTATIONS, K 2 -TREE EXHIBITS SUPERIOR PERFORMANCE IN QUERYING INDIVIDUAL POINTS, WHEREAS CKD-TREE OUTPERFORMS IN THE CONTEXT OF AGGREGATE DATA QUERIES, SUCH AS RANGE QUERIES.

WE PRESENT EFFICIENT ALGORITHMS TO COMPUTE SIMPLE AND COMPLEX MAP ALGEBRA OPERATIONS OVER RASTER DATA STORED IN MAIN MEMORY, USING THE K2-ACC COMPACT DATA STRUCTURE. RASTER DATA CORRESPOND TO NUMERICAL DATA THAT REPRESENT ATTRIBUTES OF SPATIAL OBJECTS, SUCH AS TEMPERATURE OR ELEVATION MEASURES. COMPACT DATA STRUCTURES ALLOW EFFICIENT DATA STORAGE IN MAIN MEMORY AND QUERY THEM IN THEIR COMPRESSED FORM. A K2-ACC IS A SET OF K2-TREES, ONE FOR EVERY DISTINCT NUMERIC VALUE IN THE RASTER MATRIX. WE DEMONSTRATE THAT MAP ALGEBRA OPERATIONS CAN BE COMPUTED EFFICIENTLY USING THIS COMPACT DATA STRUCTURE. IN FACT, SOME MAP ALGEBRA OPERATIONS PERFORM OVER FIVE ORDERS OF MAGNITUDE FASTER COMPARED WITH ALGORITHMS WORKING OVER UNCOMPRESSED DATASETS.

WE PRESENT EFFICIENT ALGORITHMS TO COMPUTE TWO SPATIAL QUERIES OVER POINTS STORED IN COMPACT DATA STRUCTURES. THE FORMER IS THE K-NEAREST NEIGHBORS QUERY (KNN) WHICH GIVEN A POINT Q GETS THE K-NEAREST POINTS TO Q. THE LATTER QUERY IS THE K-CLOSEST PAIR QUERY (KCPQ), WHICH OBTAINS THE K-PAIRS OF CLOSEST NEIGHBORS BETWEEN TWO SET OF POINTS R AND S ON THE SAME SPATIAL PLANE. THERE ARE SEVERAL EFFICIENT IMPLEMENTATIONS OF THESE QUERIES, WHICH WORK MAINLY WITH DATA STORED IN SECONDARY MEMORY. HOWEVER, THESE IMPLEMENTATIONS DO NOT SCALE WELL OVER LARGE DATASETS. OUR ALGORITHMS COMPUTE THE QUERIES OVER LARGE DATASETS OF POINTS STORED IN COMPACT DATA STRUCTURES, IN MAIN MEMORY. COMPACT DATA STRUCTURES ARE STRUCTURES THAT ALLOW EFFICIENTLY STORAGE DATA IN MAIN MEMORY AND QUERY THEM IN THEIR COMPRESSED FORM. WE USE THE -TREE COMPACT STRUCTURE TO REPRESENT POINTS OF INTEREST. THROUGH EXPERIMENTATION OVER SYNTHETIC AND REAL DATASETS, WE SHOW THAT BY USING THE -TREE WE CAN WORK WITH LARGE DATASETS IN MAIN MEMORY, AND THAT THE KNN AND KCPQ SPATIAL DATA QUERIES CAN BE EFFICIENTLY COMPUTED OVER THE COMPACT DATA STRUCTURES. WE ALSO IMPLEMENT A JAVA LIBRARY THAT IS AVAILABLE FOR THE ACADEMIC AND INDUSTRIAL COMMUNITY.

ABSTRACT?WE REPORT EFFICIENT ALGORITHMS TO COMPUTE THE MAP ALGEBRA OPERATIONS THRESHOLDING, SUM/MULTIPLICATION BY A SCALAR, POINT-WISE SUM, AND ZONAL SUM OVER RASTER DATA STORED IN MAIN MEMORY ON THE COMPACT DATA STRUCTURE K2-RASTER. RASTER DATA CORRESPOND TO NUMERICAL DATA, SUCH AS TEMPERATURE AND ELEVATION MEASURES RELATED TO SPATIAL OBJECTS LIKE CITIES, COUNTRIES, AMONG OTHERS. IN GENERAL, SPATIAL DATA CAN BE VERY LARGE, AND THEREFORE, THEY CAN BE STORED IN MAIN MEMORY IN COMPACT DATA STRUCTURES, WHICH ALLOW EFFICIENT DATA STORAGE AND QUERY THE DATA IN THEIR COMPRESSED FORM. ACCORDING TO THE LITERATURE, THE K2-RASTER IS THE BEST COMPACT DATA STRUCTURE TO HANDLE RASTER DATA, AND IT CORRESPONDS TO A K2 -TREE THAT STORES THE MAXIMUM AND MINIMUM VALUES FOR EACH INTERNAL NODE. WE THEORETICALLY SHOW THAT MAP ALGEBRA OPERATIONS CAN BE COMPUTED EFFICIENTLY USING A K2-RASTER COMPACT DATA STRUCTURE. IN FACT, MOST OF THE MAP ALGEBRA OPERATIONS HAVE A THEORETICAL EXPECTED TIME EQUIVALENT TO THE TIME OF TRAVERSING THE STRUCTURE.

PROXIMITY SEARCHES IN METRIC SPACES ARE RELATED WITH SEVERAL REAL WORLD APPLICATIONS, AS PATTERN RECOGNITION AND MULTIMEDIA INFORMATION RETRIEVAL. INFORMATION HAS GROWN LARGER WITH TIME, SO MEMORY EFFICIENT STRUCTURES TO STORE IT HAVE BEEN NEEDED. PROXIMITY SEARCH K NEAREST NEIGHBORS WAS IMPLEMENTED IN COMPACT DATA STRUCTURE K2TREE USING A PRIORITY QUEUE APPROACH, BEING COMPARED WITH MULTIPLE OTHERS STRUCTURES AND THEIR RESPECTIVE APPROACHES, RESULTING COMPETITIVE AMONG ALL, BUT IT IS SPECIALLY SURPASSED BY QUAD TREES WITH INCREMENTAL RADIUS APPROACH IN SYNTHETICAL DATA. IN THIS WORK, WE PROPOSE TO IMPLEMENT K NEAREST NEIGHBORS QUERY ON K2TREE USING INCREMENTAL RADIUS APPROACH WITH COMPACT COUNT, IN ORDER TO IMPROVE ITS PERFORMANCE. A THEORETICAL ANALYSIS SUPPORTS OUR PROPOSAL, AND PRELIMINARY EXPERIMENTAL RESULTS ARE SHOWN, WHERE OUR APPROACH IS COMPETITIVE. A POSSIBLE IMPROVEMENT IS DISCUSSED AFTERWARDS.

FOR OVER TWO DECADES, TURING MACHINES (TMS) HAVE BEEN STUDIED AS DYNAMICAL SYSTEMS. SEVERAL RESULTS RELATED TO TOPOLOGICAL PROPERTIES WERE ESTABLISHED, SUCH AS EQUICONTINUITY, PERIODICITY, MORTALITY, AND ENTROPY. THERE ARE TWO MAIN TOPOLOGICAL MODELS FOR TMS, AND THESE PROPERTIES STRONGLY DEPEND ON THE CONSIDERED MODEL. HERE, WE FOCUS ON TRANSITIVITY, MINIMALITY AND OTHER RELATED PROPERTIES. IN THE CONTEXT OF TMS, TRANSITIVITY REFERS TO THE EXISTENCE OF A CONFIGURATION WHOSE EVOLUTION CONTAINS EVERY POSSIBLE PATTERN OVER ANY FINITE WINDOW. MINIMALITY MEANS THAT EVERY CONFIGURATION FULFILLS THE AFOREMENTIONED STATEMENT, WHICH STRONGLY RESTRICTS TM BEHAVIOUR. THIS PAPER ESTABLISHES RELATIONS BETWEEN THE FOLLOWING PROPERTIES: TRANSITIVITY, MINIMALITY, THE EXISTENCE OF BLOCKING WORDS, APERIODICITY AND REVERSIBILITY. IT ALSO EXPLORES SOME PROPERTIES OF THE EMBEDDING TECHNIQUE, WHICH COMBINES TWO TMS TO PRODUCE A THIRD. THIS TECHNIQUE HAS BEEN USED IN PREVIOUS WORKS TO PROVE THE UNDECIDABILITY OF SEVERAL DYNAMICAL PROPERTIES. HERE, WE DEMONSTRATE ITS POWER AND VERSATILITY AND HOW THE PRODUCED MACHINE, UNDER A FEW PARTICULAR CONDITIONS, WILL INHERIT THE PROPERTIES OF ONE OF THE ORIGINAL MACHINES.

REVERSIBILITY IS EQUIVALENT TO SURJECTIVITY WITHIN TURING MACHINE TOPOLOGICAL SYSTEMS. ALTHOUGH REVERSIBILITY IS A DECIDABLE PROPERTY IN TURING MACHINES, A PROPER REVERSE TURING MACHINE DOES NOT EXIST IN THE STANDARD TURING MODEL. TRADITIONAL SOLUTIONS TO THIS PROBLEM IMPLY REDUCING THE SPEED OF THE REVERSIBLE TURING MACHINE, THEREFORE AFFECTING ITS DYNAMICS. ALSO, TRACES OF TOPOLOGICAL DYNAMICAL SYSTEMS OF TURING MACHINES CAN BE SURJECTIVE WHEN THE ORIGINAL TURING MACHINE IS NOT. A SOLUTION IS A REVERSIBLE TURING MACHINE, CONSIDERING A SHIFT IN THE TAPE DEPENDING ON THE ACTUAL STATE, AND ALSO IT IS PROVEN THAT SURJECTIVITY IS UNDECIDABLE FOR TURING MACHINE SUBSHIFTS ONLY WHEN THE RADIUS IS 0.

OVER THE PAST FEW DECADES, TURING MACHINES HAVE BEEN STUDIED AS DYNAMICAL SYSTEMS, WITH THE FOCUS BEING ON THEIR BEHAVIOR RATHER THAN THEIR RESULTS. NOTEWORTHY RESULTS CONCERNING TOPOLOGICAL AND DYNAMICAL PROPERTIES, SUCH AS THE EXISTENCE AND UNDECIDABILITY OF TOPOLOGICAL TRANSITIVITY IN TMH AND TOPOLOGICAL MINIMALITY IN TMT, WERE ESTABLISHED. BOTH PROPERTIES ARE RELATED TO REACHING FINITE WINDOWS FROM SOME OR ANY POSSIBLE CONFIGURATION. NONETHELESS, BOTH PROPERTIES EXHIBIT NO RESTRICTION OVER THE TIME A MACHINE TAKES TO REACH THESE FINITE WINDOWS. IN THIS ARTICLE, WE FOCUS ON THE MIXING NOTIONS: WEAK MIXING, TOTAL TRANSITIVITY AND TOPOLOGICAL MIXING. THESE PROPERTIES ARE RELATED TO A TIME WINDOW OR GAP WHERE FINITE CONFIGURATIONS MUST REACH ONE ANOTHER. IN THIS ARTICLE, WE ANALYZE THE SMART MACHINE TO PROVE THAT ITS TMT DYNAMICAL MODEL IS TOPOLOGICALLY WEAK MIXING (AND THEREFORE TOTALLY TRANSITIVE) AND THAT ALL MIXING NOTIONS ARE UNDECIDABLE.

IN 2014, JEANDEL PROVED THAT TWO DYNAMICAL PROPERTIES REGARDING TURING MACHINES CAN BE COMPUTABLE WITH ANY DESIRED ERROR , THE TURING MACHINE MAXIMUM SPEED AND TOPOLOGICAL ENTROPY. BOTH PROBLEMS WERE PROVED IN PARALLEL, USING EQUIVALENT PROPERTIES. THOSE RESULTS WERE UNEXPECTED, AS MOST (IF NOT ALL) DYNAMICAL PROPERTIES ARE UNDECIDABLE. NEVERTHELESS, TOPOLOGICAL ENTROPY POSITIVENESS FOR REVERSIBLE AND COMPLETE TURING MACHINES WAS SHORTLY PROVED TO BE UNDECIDABLE, WITH A REDUCTION OF THE HALTING PROBLEM WITH EMPTY COUNTERS IN 2-REVERSIBLE COUNTER MACHINES. UNFORTUNATELY, THE SAME PROOF COULD NOT BE USED TO PROVE UNDECIDABILITY OF SPEED POSITIVENESS. IN THIS RESEARCH, WE PROVE THE UNDECIDABILITY OF HOMOGENEOUS TAPE REACHABILITY PROBLEM FOR APERIODIC AND REVERSIBLE TURING MACHINES, IN ORDER TO USE IT TO PROVE THE UNDECIDABILITY OF THE SPEED POSITIVENESS PROBLEM FOR COMPLETE AND REVERSIBLE TURING MACHINES.