In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory. == Minimal DFA == For each regular language, there also exists a minimal automaton that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names). The minimal DFA ensures minimal computational cost for tasks such as pattern matching. There are three classes of states that can be removed or merged from the original DFA without affecting the language it accepts. Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string. These states can be removed. Dead states are the states from which no final state is reachable. These states can be removed unless the automaton is required to be complete. Nondistinguishable states are those that cannot be distinguished from one another for any input string. These states can be merged. DFA minimization is usually done in three steps: remove dead and unreachable states (this will accelerate the following step), merge nondistinguishable states, optionally, re-create a single dead state ("sink" state) if the resulting DFA is required to be complete. == Unreachable states == The state p {\displaystyle p} of a deterministic finite automaton M = ( Q , Σ , δ , q 0 , F ) {\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)} is unreachable if no string w {\displaystyle w} in Σ ∗ {\displaystyle \Sigma ^{}} exists for which p = δ ∗ ( q 0 , w ) {\displaystyle p=\delta ^{}(q_{0},w)} . In this definition, Q {\displaystyle Q} is the set of states, Σ {\displaystyle \Sigma } is the set of input symbols, δ {\displaystyle \delta } is the transition function (mapping a state and an input symbol to a set of states), δ ∗ {\displaystyle \delta ^{}} is its extension to strings (also known as extended transition function), q 0 {\displaystyle q_{0}} is the initial state, and F {\displaystyle F} is the set of accepting (also known as final) states. Reachable states can be obtained with the following algorithm: Assuming an efficient implementation of the state sets (e.g. new_states) and operations on them (such as adding a state or checking whether it is present), this algorithm can be implemented with time complexity O ( n + m ) {\displaystyle O(n+m)} , where n {\displaystyle n} is the number of states and m {\displaystyle m} is the number of transitions of the input automaton. Unreachable states can be removed from the DFA without affecting the language that it accepts. == Nondistinguishable states == The following algorithms present various approaches to merging nondistinguishable states. === Hopcroft's algorithm === One algorithm for merging the nondistinguishable states of a DFA, due to Hopcroft (1971), is based on partition refinement, partitioning the DFA states into groups by their behavior. These groups represent equivalence classes of the Nerode congruence, whereby every two states are equivalent if they have the same behavior for every input sequence. That is, for every two states p1 and p2 that belong to the same block of the partition P, and every input word w, the transitions determined by w should always take states p1 and p2 to either states that both accept or states that both reject. It should not be possible for w to take p1 to an accepting state and p2 to a rejecting state or vice versa. The following pseudocode describes the form of the algorithm as given by Xu. Alternative forms have also been presented. The algorithm starts with a partition that is too coarse: every pair of states that are equivalent according to the Nerode congruence belong to the same set in the partition, but pairs that are inequivalent might also belong to the same set. It gradually refines the partition into a larger number of smaller sets, at each step splitting sets of states into pairs of subsets that are necessarily inequivalent. The initial partition is a separation of the states into two subsets of states that clearly do not have the same behavior as each other: the accepting states and the rejecting states. The algorithm then repeatedly chooses a set A from the current partition and an input symbol c, and splits each of the sets of the partition into two (possibly empty) subsets: the subset of states that lead to A on input symbol c, and the subset of states that do not lead to A. Since A is already known to have different behavior than the other sets of the partition, the subsets that lead to A also have different behavior than the subsets that do not lead to A. When no more splits of this type can be found, the algorithm terminates. Lemma. Given a fixed character c and an equivalence class Y that splits into equivalence classes B and C, only one of B or C is necessary to refine the whole partition. Example: Suppose we have an equivalence class Y that splits into equivalence classes B and C. Suppose we also have classes D, E, and F; D and E have states with transitions into B on character c, while F has transitions into C on character c. By the Lemma, we can choose either B or C as the distinguisher, let's say B. Then the states of D and E are split by their transitions into B. But F, which doesn't point into B, simply doesn't split during the current iteration of the algorithm; it will be refined by other distinguisher(s). Observation. All of B or C is necessary to split referring classes like D, E, and F correctly—subsets won't do. The purpose of the outermost if statement (if Y is in W) is to patch up W, the set of distinguishers. We see in the previous statement in the algorithm that Y has just been split. If Y is in W, it has just become obsolete as a means to split classes in future iterations. So Y must be replaced by both splits because of the Observation above. If Y is not in W, however, only one of the two splits, not both, needs to be added to W because of the Lemma above. Choosing the smaller of the two splits guarantees that the new addition to W is no more than half the size of Y; this is the core of the Hopcroft algorithm: how it gets its speed, as explained in the next paragraph. The worst case running time of this algorithm is O(ns log n), where n is the number of states and s is the size of the alphabet. This bound follows from the fact that, for each of the ns transitions of the automaton, the sets drawn from Q that contain the target state of the transition have sizes that decrease relative to each other by a factor of two or more, so each transition participates in O(log n) of the splitting steps in the algorithm. The partition refinement data structure allows each splitting step to be performed in time proportional to the number of transitions that participate in it. This remains the most efficient algorithm known for solving the problem, and for certain distributions of inputs its average-case complexity is even better, O(n log log n). Once Hopcroft's algorithm has been used to group the states of the input DFA into equivalence classes, the minimum DFA can be constructed by forming one state for each equivalence class. If S is a set of states in P, s is a state in S, and c is an input character, then the transition in the minimum DFA from the state for S, on input c, goes to the set containing the state that the input automaton would go to from state s on input c. The initial state of the minimum DFA is the one containing the initial state of the input DFA, and the accepting states of the minimum DFA are the ones whose members are accepting states of the input DFA. === Moore's algorithm === Moore's algorithm for DFA minimization is due to Edward F. Moore (1956). Like Hopcroft's algorithm, it maintains a partition that starts off separating the accepting from the rejecting states, and repeatedly refines the partition until no more refinements can be made. At each step, it replaces the current partition with the coarsest common refinement of s + 1 partitions, one of which is the current one and the rest of which are the preimages of the current partition under the transition functions for each of the input symbols. The algorithm terminates when this replacement does not change the current partition. Its worst-case time complexity is O(n2s): each step of the algorithm may be performed in time O(ns) using a variant of radix sort to reorder the states so that states in the same set of the new partition are consecutive in the ordering, and there are at most n steps since each one but the last increases the number of sets in the partition. The instances of the DFA minimization problem that cause the worst-case behavior are the same as for Hopcroft's algorithm. The number of steps th
XRX (web application architecture)
In software development XRX is a web application architecture based on XForms, REST and XQuery. XRX applications store data on both the web client and on the web server in XML format and do not require a translation between data formats. XRX is considered a simple and elegant application architecture due to the minimal number of translations needed to transport data between client and server systems. The XRX architecture is also tightly coupled to W3C standards (CSS, XHTML 2.0, XPath, XML Schema) to ensure XRX applications will be robust in the future. Because XRX applications leverage modern declarative languages on the client and functional languages on the server they are designed to empower non-developers who are not familiar with traditional imperative languages such as JavaScript, Java or .Net. == Overview of XRX == XRX is a zero translation application architecture that uses XML to store data in the client web browser, on the application server and in the database server. It is because each of these layers uses XML as the same structural data model that XRX applications do not have to translate data structures to and from both object and relational data structures. Because of the lack of need for translation, XRX is considered to have a clean and elegant design. The XRX web application architecture allows developers to focus on the business problem and not the translation problem. XRX benefits from several advances in software technology: === Client Architectural Features === A model–view–controller (MVC) architecture that separates the data from its presentation and business logic. A single element (xf:submission) for all server submissions. This replaces much of the JavaScript code required in most AJAX applications. An advanced event model (XML Events) consistent with W3C standards that frees applications from having to deal with vendor-specific and browser-specific event handling. A Dependency graph that is used to store the dependency structure of the client controllers. This frees the developer from having to manually update either the model or the views when data changes in an application. This allows spreadsheet-like applications to be created on the client with very little effort. A declarative programming style that allows most client XForms applications to be created using a small set of approximately 20 elements. This allows rich client applications to be created without knowledge of JavaScript or other procedural scripting languages. An easy-to-extend system for creating new user interface controls using the EXtensible Bindings Language. This allows developers to add new controls at any time without fear of incompatibilities with W3C standards. === Server Architecture Features === Many native XML databases have built-in REST interfaces making each XQuery inherently a RESTful web service. A functional programming model that promotes side-effect free systems that are easier to debug and easier to run on multiple processors. An easy-to-extend system using XQuery function and modules. === Both Client and Server === Both XRX client and server components support a wide range of XML related standards such as XPath, XML Schema and XML Namespaces. Consistent use of REST interfaces to exchange data between the client and server for all transfers of data including as-you-type data checking and suggest functions. Consistent integration of W3C standards including use of XPath and XML Schema data types. A large library of standard of functions used on both the client and server. == Overall Benefits of XRX == One of the principal benefits of the XRX architecture is that it avoids the requirement to "shred" complex data structures into relational structures and then reconstitute the data back into structures when a record is edited on the client. Another benefits of the XRX Web application architecture is that it avoids most of the problems around the object-relational impedance mismatch. Another advantage is that the client developer does not have to learn JavaScript on the client. == Comparison with Traditional Object/Relational Web Application Architectures == Many traditional web application architectures created in the late 1990 were based on middle object tiers and persistence layers that used tabular data streams and relational database systems. Because each of these layers used different structures to store the models the systems required much additional complexity to translate between layers. == History of XRX == Early examples of using a zero-translation architecture in multi-tier systems can be traced back to the rise of object-oriented databases in the 1990s. See OODBMS History Mark Birbeck suggested that the combination of XForms, XQuery with REST interfaces between the two had many advantages in a meeting to the UK XML User Group in September 2006 . His presentation was one of the first to specifically suggest that the combination of three technologies: XForms and XQuery with REST interfaces would have surprisingly beneficial effects. Mark termed this process "Skimming" but that term did not seem to be contagious. Erik Bruchez of Orbeon spoke at the XML 2007 conference on Boston in December 2007. In his presentation "XForms and the eXist XML database: a perfect couple", Bruchez showed that many people were discovering synergistic benefits of XForms on the client and XQuery on the server. The label for XRX was suggested by a blog posting by Dan McCreary on December 14, 2007. It was in this article that Dan suggested the need for a contagious meme for the ideas behind the XRX architecture. == Generalizations of XRX == Although XRX was originally intended to connote the use of XForms on the client, REST as an interface and XQuery on the server, other proponents of the symmetrical use of XML on the client and server have generalized the term to encompass any XML-centric web client and any server that can store and query XML documents. This use of XRX is generally referred to as "shallow XRX". These generalizations do benefit from a simplified zero-translation architecture but many do not benefit from REST interfaces, XPath for consistent data selection, declarative systems in the client, and functional languages on the server (one of the key aspects of XRX). Use of all three technologies (XForms, REST and XQuery) is referred to as "deep XRX". Although XRX architecture is centred on XForms and XQuery, it does not preclude the use of other technologies that manipulate XML natively, such as XSLT, XProc, and XSL-FO.
Google Messages
Google Messages (formerly known as Messenger, Android Messages, and Messages by Google) is a text messaging software application developed by Google for its Android and Wear OS mobile operating systems. It is also available as a web app. Google's official universal messaging platform for the Android ecosystem, Messages employs SMS, MMS, and Rich Communication Services (RCS). Starting in 2023, Google has RCS activated by default on participating Android devices, similar to the implementation of iMessage on Apple devices. Samsung Messages will be discontinued on July 6th 2026, with Samsung transitioning users to Google Messages as the default messaging application. == History == The original code for Android SMS messaging was released in 2009 integrated into the operating system. It was released as a standalone application independent of Android with the release of Android 5.0 Lollipop in 2014, replacing Google Hangouts as the default SMS app on Google's Nexus line of phones. In 2018, Messages adopted RCS messages and evolved to send larger data files, sync with other apps, and even create mass messages. This was in preparation for when Google launched Messages for web. In December 2019, Google began to introduce support for Rich Communication Services (RCS) messaging via an RCS service hosted by Google, referred to in the user interface as "chat features". This was followed by a wider global rollout throughout 2020. The app surpassed 1 billion installs in April 2020, doubling its number of installs in less than a year. Initially, RCS did not support end-to-end encryption. In June 2021, Google introduced end-to-end encryption in Messages by default using the Signal Protocol, for all one-to-one RCS-based conversations, for all RCS group chats in December 2022 for beta users, and for all RCS users by August 2023, as well as enabling RCS for all users by default to encourage encryption. In July 2023, Google announced it would build the Message Layer Security (MLS) end-to-end encryption protocol into Google Messages. Beginning with the Samsung Galaxy S21, Messages replaces Samsung's in-house Messages app as the default text messaging app for One UI for some regions and carriers. In April 2021, the app began to receive UI modifications on Samsung devices to follow aspects of One UI, including pushing the top of the message list towards the middle of the screen to improve ergonomics. In February 2023, Google began to replace references to "chat features" in the Messages user interface with "RCS". In August 2023, Google announced that Messages will use RCS by default for all users unless they opt out, to allow them to benefit from secure messaging. In December 2023, with the arrival of several new features, the app was renamed "Google Messages". In July 2024, Samsung announced it would no longer pre-install Samsung Messages on its Galaxy devices in some regions, starting with the Galaxy Z Fold 6 and Flip, favoring Google Messages instead. In April 2026, Samsung announced that Samsung Messages would be discontinued in July 2026. It encouraged users to switch to Google Messages. == Features == Some of the most important features in Google Messages are: Send instant text and voice messages in 1:1 or group chat conversations over mobile data and Wi-Fi, via Android, Wear OS or the web. End-to-end encryption for RCS chats. Typing, sent, delivered and read status Reply and react to specific messages Share files and high-resolution photos Voice message transcriptions Schedule messages In-app reminders for birthdays and messages you didn't respond to after some time with Nudges Tight integration with the Google ecosystem, e.g. Google Calendar, Meet, Maps, YouTube, Photos, Contacts, Assistant, Search, Safe Browsing etc. Web interface: Users can visit https://messages.google.com/web and either sign in with their Google account or scan the QR code that is shown with their smartphone to access a limited web version of the app that allows them to send and receive messages, provided the smartphone remains connected. Phone number recognition: The app shows the country and province of the caller. Additionally, it can show the company's name or a warning for spam calls if the number is registered in a data base. Access to the Gemini chatbot on select Pixel, Galaxy and Android devices.
Cloud Native Computing Foundation
The Cloud Native Computing Foundation (CNCF) is a subsidiary of the Linux Foundation founded in 2015 to support cloud-native computing. == History == It was announced alongside Kubernetes 1.0, an open source container cluster manager, which was contributed to the Linux Foundation by Google as a seed technology. Founding members include Google, CoreOS, Mesosphere, Red Hat, Twitter, Huawei, Intel, RX-M, Cisco, IBM, Docker, Univa, and VMware. Today, CNCF is supported by over 450 members. In August 2018 Google announced that it was handing over operational control of Kubernetes to the community. == Projects == Argo is a collection of tools for getting work done with Kubernetes. Among its main features are Workflows and Events. It was accepted to CNCF on March 26, 2020 at the Incubating maturity level and then moved to the Graduated maturity level on December 6, 2022. cert-manager provisions and manages TLS certificates in Kubernetes. It was accepted to CNCF on November 10, 2020, moved to the Incubating maturity level on September 19, 2022, and then moved to the Graduated maturity level on September 29, 2024. Cilium provides networking, security, and observability for Kubernetes deployments using eBPF technology. It joined the CNCF at incubation level in October 2021 and the CNCF announced its graduation in October 2023. containerd is an industry-standard core container runtime. It is currently available as a daemon for Linux and Windows, which can manage the complete container lifecycle of its host system. In 2015, Docker donated the OCI Specification to The Linux Foundation with a reference implementation called runc. Since February 28, 2019 it is an official CNCF project. Its general availability and intention to donate the project to CNCF was announced by Docker in 2017. CoreDNS is a DNS server that chains plugins. Its graduation was announced in 2019. Dapr, the distributed application runtime, provides APIs for building secure and reliable microservices and agentic AI systems. Dapr was donated to the CNCF in November 2021 and joined at incubation level. The CNCF announced its graduation in November 2024. Envoy: Originally built at Lyft to move their architecture away from a monolith, Envoy is a high-performance open source edge and service proxy that makes the network transparent to applications. Lyft contributed Envoy to Cloud Native Computing Foundation in September 2017. etcd is a distributed key value store, providing a method of storing data across a cluster of machines. It became a CNCF incubating project in 2018 at KubeCon+CloudNativeCon North America in Seattle that year. Falco is an open source and cloud native runtime security initiative. It is the "de facto Kubernetes threat detection engine". It became an incubating project in January 2020 and graduated in February 2024. Flux is an open source project for powering GitOps in Kubernetes clusters. It provides the GitOps Toolkit, a set of Kubernetes APIs that allow you to define how configuration source code is securely pulled into your cluster and deployed by popular Kubernetes manifests rendering engines like Kustomize and Helm. The most recommended source mechanism is the OCIRepository API, which provides enhanced security and benefits from container image tooling out there. Flux has also notification integrations with popular services like Prometheus Alertmanager, PagerDuty, Slack and so on. Flux has graduated in CNCF in 2022. Harbor is an "open source trusted cloud native registry project that stores, signs, and scans content." It became an incubating project in September 2019 and graduated in June 2020. Helm is a package manager that helps developers "easily manage and deploy applications onto the Kubernetes cluster." It joined the incubating level in June 2018 and graduated in April 2020. Istio is a service mesh technology. It was accepted by CNCF in September 2022 and graduated on July 12, 2023. Jaeger, Created by Uber Engineering, Jaeger is an open source distributed tracing system inspired by Google Dapper paper and OpenZipkin community. It can be used for tracing microservice-based architectures, including distributed context propagation, distributed transaction monitoring, root cause analysis, service dependency analysis, and performance/latency optimization. The Cloud Native Computing Foundation Technical Oversight Committee voted to accept Jaeger as the 12th hosted project in September 2017 and became a graduated project in 2019. In 2020 it became an approved and fully integrated part of the CNCF ecosystem. Kubernetes is an open source framework for automating deployment and managing applications in a containerized and clustered environment. "It aims to provide better ways of managing related, distributed components across the varied infrastructure." It was originally designed by Google and donated to The Linux Foundation to form the Cloud Native Computing Foundation with Kubernetes as the seed technology. The "large and diverse" community supporting the project has made its staying power more robust than other, older technologies of the same ilk. In January 2020, the CNCF annual report showed significant growth in interest, training, event attendance and investment related to Kubernetes. Linkerd is CNCF's fifth member project, and the project that coined the term "service mesh". Linkerd adds observability, security, and reliability features to applications by adding them to the platform rather than the application layer, and features a "micro-proxy" to maximize speed and security of its data plane. Linkerd graduated from CNCF in July 2021. Open Policy Agent (OPA) is "an open source general-purpose policy engine and language for cloud infrastructure." It became a CNCF incubating project in April 2019. OPA graduated from CNCF in February 2021. Prometheus is a cloud monitoring tool sponsored by SoundCloud in early iterations. In August 2018, the tool was designated a graduated project by the Cloud Native Computing Foundation. It is now a Cloud Native Computing Foundation member project. Rook is CNCF's first cloud native storage project. It became an incubation level project in 2018 and graduated in October 2020. SPIFFE is an open standard and framework for workload identity, much the same way that OAuth is an open standard and framework for human identity. It is built from the ground up to accommodate modern computing environments, which operate with systems scale and velocity (as opposed to human scale and velocity), while still maintaining interoperability with existing technologies like OAuth and X.509 Public key infrastructure. Unlike other identity standards, SPIFFE supports multiple credential types for a single identity, ensuring that the highly varied needs of production environments are consistently met without compromise. SPIFFE joined the CNCF as a sandbox project in 2018, was accepted to incubation in 2020, and graduated in 2022. SPIRE is an open source identity provider for workloads based on the SPIFFE framework. It is highly pluggable, and fills the attestation and issuance needs required by any workload identity solution. The plugin interfaces it exposes allows users to write integrations with in-house systems, build internal self-service portals, and more. It is a very powerful building block for issuing short-lived identity credentials to dynamic cloud workloads. SPIRE became a CNCF Graduated project in 2022. The Update Framework (TUF) helps developers to secure new or existing software update systems, which are often found to be vulnerable to many known attacks. TUF addresses this widespread problem by providing a comprehensive, flexible security framework that developers can integrate with any software update system. TUF was CNCF's first security-focused project and the ninth project overall to graduate from the foundation's hosting program. TiKV provides a distributed key–value database. Vitess is a database clustering system for horizontal scaling of MySQL, first created for internal use by YouTube. It became a CNCF project in 2018 and graduated in November 2019. Contour is a management server for Envoy that can direct the management of Kubernetes' traffic. Contour also provides routing features that are more advanced than Kubernetes' out-of-the-box Ingress specification. VMWare contributed the project to CNCF in July 2020. Cortex offers horizontally scalable, multi-tenant, long-term storage for Prometheus and works alongside Amazon DynamoDB, Google Bigtable, Cassandra, S3, GCS, and Microsoft Azure. It was introduced into the ecosystem incubator alongside Thanos in August 2020. CRI-O is an Open Container Initiative (OCI) based "implementation of Kubernetes Container Runtime Interface". CRI-O allows Kubernetes to be container runtime-agnostic. It became an incubating project in 2019. gRPC is a "modern open source high performance RPC framework that can run in any environment." The project was formed in 2015 when Google decided to open sou
Software design
Software design is the process of conceptualizing how a software system will work before it is implemented or modified. Software design also refers to the direct result of the design process – the concepts of how the software will work which may be formally documented or may be maintained less formally, including via oral tradition. The design process enables a designer to model aspects of a software system before it exists with the intent of making the effort of writing the code more efficiently. Creativity, past experience, a sense of what makes "good" software, and a commitment to quality are success factors for a competent design. A software design can be compared to an architected plan for a house. High-level plans represent the totality of the house (e.g., a three-dimensional rendering of the house). Lower-level plans provide guidance for constructing each detail (e.g., the plumbing lay). Similarly, the software design model provides a variety of views of the proposed software solution. == Part of the overall process == In terms of the waterfall development process, software design is the activity that occurs after requirements analysis and before coding. Requirements analysis determines what the system needs to do without determining how it will do it, and thus, multiple designs can be imagined that satisfy the requirements. The design can be created while coding, without a plan or requirements analysis, but for more complex projects this is less feasible. Completing a design prior to coding allows for multidisciplinary designers and subject-matter experts to collaborate with programmers to produce software that is useful and technically sound. Sometimes, a simulation or prototype is created to model the system in an effort to determine a valid and good design. == Code as design == A common point of confusion with the term design in software is that the process applies at multiple levels of abstraction such as a high-level software architecture and lower-level components, functions and algorithms. A relatively formal process may occur at high levels of abstraction but at lower levels, the design process is almost always less formal where the only artifact of design may be the code itself. To the extent that this is true, software design refers to the design of the design. Edsger W. Dijkstra referred to this layering of semantic levels as the "radical novelty" of computer programming, and Donald Knuth used his experience writing TeX to describe the futility of attempting to design a program prior to implementing it: TEX would have been a complete failure if I had merely specified it and not participated fully in its initial implementation. The process of implementation constantly led me to unanticipated questions and to new insights about how the original specifications could be improved. == Artifacts == A design process may include the production of art Software design documentation such as flow chart, use case, Pseudocode, Unified Modeling Language model and other Fundamental modeling concepts. For user centered software, design may involve user experience design yielding a storyboard to help determine those specifications. Documentation may be reviewed to allow constraints, specifications and even requirements to be adjusted prior to coding. == Iterative design == Software systems inherently deal with uncertainties, and the size of software components can significantly influence a system's outcomes, both positively and negatively. Neal Ford and Mark Richards propose an iterative approach to address the challenge of identifying and right-sizing components. This method emphasizes continuous refinement as teams develop a more nuanced understanding of system behavior and requirements. The approach typically involves a cycle with several stages: A high-level partitioning strategy is established, often categorized as technical or domain-based. Guidelines for the smallest meaningful deployable unit, referred to as "quanta," are defined. While these foundational decisions are made early, they may be revisited later in the cycle if necessary. Initial components are identified based on the established strategy. Requirements are assigned to the identified components. The roles and responsibilities of each component are analyzed to ensure clarity and minimize overlap. Architectural characteristics, such as scalability, fault tolerance, and maintainability, are evaluated. Components may be restructured based on feedback from development teams. This cycle serves as a general framework and can be adapted to different domains. == Design principles == Design principles enable a software engineer to navigate the design process. Davis suggested principles which have been refined over time as: The design process should not suffer from "tunnel vision" A good designer should consider alternative approaches, judging each based on the requirements of the problem, the resources available to do the job. The design should be traceable to the analysis model Because a single element of the design model can often be traced back to multiple requirements, it is necessary to have a means for tracking how requirements have been satisfied by the design model. The design should not reinvent the wheel Systems are constructed using a set of design patterns, many of which have likely been encountered before. These patterns should always be chosen as an alternative to reinvention. Time is short and resources are limited; design time should be invested in representing (truly new) ideas by integrating patterns that already exist (when applicable). The design should "minimize the intellectual distance" between the software and the problem as it exists in the real world That is, the structure of the software design should, whenever possible, mimic the structure of the problem domain. The design should exhibit uniformity and integration A design is uniform if it appears fully coherent. In order to achieve this outcome, rules of style and format should be defined for a design team before design work begins. A design is integrated if care is taken in defining interfaces between design components. The design should be structured to accommodate change The design concepts discussed in the next section enable a design to achieve this principle. The design should be structured to degrade gently, even when aberrant data, events, or operating conditions are encountered Well-designed software should never "bomb"; it should be designed to accommodate unusual circumstances, and if it must terminate processing, it should do so in a graceful manner. Design is not coding, coding is not design Even when detailed procedural designs are created for program components, the level of abstraction of the design model is higher than the source code. The only design decisions made at the coding level should address the small implementation details that enable the procedural design to be coded. The design should be assessed for quality as it is being created, not after the fact A variety of design concepts and design measures are available to assist the designer in assessing quality throughout the development process. The design should be reviewed to minimize conceptual (semantic) errors There is sometimes a tendency to focus on minutiae when the design is reviewed, missing the forest for the trees. A design team should ensure that major conceptual elements of the design (omissions, ambiguity, inconsistency) have been addressed before worrying about the syntax of the design model. == Design concepts == Design concepts provide a designer with a foundation from which more sophisticated methods can be applied. Design concepts include: Abstraction Reducing the information content of a concept or an observable phenomenon, typically to retain only information that is relevant for a particular purpose. It is an act of Representing essential features without including the background details or explanations. Architecture The overall structure of the software and the ways in which that structure provides conceptual integrity for a system. Good software architecture will yield a good return on investment with respect to the desired outcome of the project, e.g. in terms of performance, quality, schedule and cost. Control hierarchy A program structure that represents the organization of a program component and implies a hierarchy of control. Data structure Representing the logical relationship between elements of data. Design pattern A designer may identify a design aspect of the system that has solved in the past. The reuse of such patterns can increase software development velocity. Information hiding Modules should be specified and designed so that information contained within a module is inaccessible to other modules that have no need for such information. Modularity Dividing the solution into parts (modules). Refinement The process of elaboration. A hierarchy is developed by decomposing a macrosco
Embodied cognitive science
Embodied cognitive science is an interdisciplinary field of research, the aim of which is to explain the mechanisms underlying intelligent behavior. It comprises three main methodologies: the modeling of psychological and biological systems in a holistic manner that considers the mind and body as a single entity; the formation of a common set of general principles of intelligent behavior; and the experimental use of robotic agents in controlled environments. == Contributors == Embodied cognitive science borrows heavily from embodied philosophy and the related research fields of cognitive science, psychology, neuroscience and artificial intelligence. Contributors to the field include: From the perspective of neuroscience, Gerald Edelman of the Neurosciences Institute at La Jolla, Francisco Varela of CNRS in France, and J. A. Scott Kelso of Florida Atlantic University From the perspective of psychology, Lawrence Barsalou, Michael Turvey, Vittorio Guidano and Eleanor Rosch From the perspective of linguistics, Gilles Fauconnier, George Lakoff, Mark Johnson, Leonard Talmy and Mark Turner From the perspective of language acquisition, Eric Lenneberg and Philip Rubin at Haskins Laboratories From the perspective of anthropology, Edwin Hutchins, Bradd Shore, James Wertsch and Merlin Donald. From the perspective of autonomous agent design, early work is sometimes attributed to Rodney Brooks or Valentino Braitenberg From the perspective of artificial intelligence, Understanding Intelligence by Rolf Pfeifer and Christian Scheier or How the Body Shapes the Way We Think, by Rolf Pfeifer and Josh C. Bongard From the perspective of philosophy, Andy Clark, Dan Zahavi, Shaun Gallagher, and Evan Thompson In 1950, Alan Turing proposed that a machine may need a human-like body to think and speak: It can also be maintained that it is best to provide the machine with the best sense organs that money can buy, and then teach it to understand and speak English. That process could follow the normal teaching of a child. Things would be pointed out and named, etc. Again, I do not know what the right answer is, but I think both approaches should be tried. == Traditional cognitive theory == Embodied cognitive science is an alternative theory to cognition in which it minimizes appeals to computational theory of mind in favor of greater emphasis on how an organism's body determines how and what it thinks. Traditional cognitive theory is based mainly around symbol manipulation, in which certain inputs are fed into a processing unit that produces an output. These inputs follow certain rules of syntax, from which the processing unit finds semantic meaning. Thus, an appropriate output is produced. For example, a human's sensory organs are its input devices, and the stimuli obtained from the external environment are fed into the nervous system which serves as the processing unit. From here, the nervous system is able to read the sensory information because it follows a syntactic structure, thus an output is created. This output then creates bodily motions and brings forth behavior and cognition. Of particular note is that cognition is sealed away in the brain, meaning that mental cognition is cut off from the external world and is only possible by the input of sensory information. == The embodied cognitive approach == Embodied cognitive science differs from the traditionalist approach in that it denies the input-output system. This is chiefly due to the problems presented by the Homunculus argument, which concluded that semantic meaning could not be derived from symbols without some kind of inner interpretation. If some little man in a person's head interpreted incoming symbols, then who would interpret the little man's inputs? Because of the specter of an infinite regress, the traditionalist model began to seem less plausible. Thus, embodied cognitive science aims to avoid this problem by defining cognition in three ways. === Physical attributes of the body === The first aspect of embodied cognition examines the role of the physical body, particularly how its properties affect its ability to think. This part attempts to overcome the symbol manipulation component that is a feature of the traditionalist model. Depth perception, for instance, can be better explained under the embodied approach due to the sheer complexity of the action. Depth perception requires that the brain detect the disparate retinal images obtained by the distance of the two eyes. In addition, body and head cues complicate this further. When the head is turned in a given direction, objects in the foreground will appear to move against objects in the background. From this, it is said that some kind of visual processing is occurring without the need of any kind of symbol manipulation. This is because the objects appearing to move the foreground are simply appearing to move. This observation concludes then that depth can be perceived with no intermediate symbol manipulation necessary. A more poignant example exists through examining auditory perception. Generally speaking the greater the distance between the ears, the greater the possible auditory acuity. Also relevant is the amount of density in between the ears, for the strength of the frequency wave alters as it passes through a given medium. The brain's auditory system takes these factors into account as it process information, but again without any need for a symbolic manipulation system. This is because the distance between the ears for example does not need symbols to represent it. The distance itself creates the necessary opportunity for greater auditory acuity. The amount of density between the ears is similar, in that it is the actual amount itself that simply forms the opportunity for frequency alteration. Thus under consideration of the physical properties of the body, a symbolic system is unnecessary and an unhelpful metaphor. === The body's role in the cognitive process === The second aspect draws heavily from George Lakoff's and Mark Johnson's work on concepts. They argued that humans use metaphors whenever possible to better explain their external world. Humans also have a basic stock of concepts in which other concepts can be derived from. These basic concepts include spatial orientations such as up, down, front, and back. Humans can understand what these concepts mean because they can directly experience them from their own bodies. For example, because human movement revolves around standing erect and moving the body in an up-down motion, humans innately have these concepts of up and down. Lakoff and Johnson contend this is similar with other spatial orientations such as front and back too. As mentioned earlier, these basic stocks of spatial concepts are the basis in which other concepts are constructed. Happy and sad for instance are seen now as being up or down respectively. When someone says they are feeling down, what they are really saying is that they feel sad for example. Thus the point here is that true understanding of these concepts is contingent on whether one can have an understanding of the human body. So the argument goes that if one lacked a human body, they could not possibly know what up or down could mean, or how it could relate to emotional states. [I]magine a spherical being living outside of any gravitational field, with no knowledge or imagination of any other kind of experience. What could UP possibly mean to such a being? While this does not mean that such beings would be incapable of expressing emotions in other words, it does mean that they would express emotions differently from humans. Human concepts of happiness and sadness would be different because human would have different bodies. So then an organism's body directly affects how it can think, because it uses metaphors related to its body as the basis of concepts. === Interaction of local environment === A third component of the embodied approach looks at how agents use their immediate environment in cognitive processing. Meaning, the local environment is seen as an actual extension of the body's cognitive process. The example of a personal digital assistant (PDA) is used to better imagine this. Echoing functionalism (philosophy of mind), this point claims that mental states are individuated by their role in a much larger system. So under this premise, the information on a PDA is similar to the information stored in the brain. So then if one thinks information in the brain constitutes mental states, then it must follow that information in the PDA is a cognitive state too. Consider also the role of pen and paper in a complex multiplication problem. The pen and paper are so involved in the cognitive process of solving the problem that it seems ridiculous to say they are somehow different from the process, in very much the same way the PDA is used for information like the brain. Another example examines how humans control and manipulate their environment
Color space
A color space is a specific organization of colors. In combination with color profiling supported by various physical devices, it supports reproducible representations of color – whether such representation entails an analog or a digital representation. A color space may be arbitrary, i.e. with physically realized colors assigned to a set of physical color swatches with corresponding assigned color names (including discrete numbers in – for example – the Pantone collection), or structured with mathematical rigor (as with the NCS System, Adobe RGB and sRGB). A "color space" is a useful conceptual tool for understanding the color capabilities of a particular device or digital file. When trying to reproduce color on another device, color spaces can show whether shadow/highlight detail and color saturation can be retained, and by how much either will be compromised. A "color model" is an abstract mathematical model describing the way colors can be represented as tuples of numbers (e.g. triples in RGB or quadruples in CMYK); however, a color model with no associated mapping function to an absolute color space is a more or less arbitrary color system with no connection to any globally understood system of color interpretation. Adding a specific mapping function between a color model and a reference color space establishes within the reference color space a definite "footprint", known as a gamut, and for a given color model, this defines a color space. For example, Adobe RGB and sRGB are two different absolute color spaces, both based on the RGB color model. When defining a color space, the usual reference standard is the CIELAB or CIEXYZ color spaces, which were specifically designed to encompass all colors the average human can see. Since "color space" identifies a particular combination of the color model and the mapping function, the word is often used informally to identify a color model. However, even though identifying a color space automatically identifies the associated color model, this usage is incorrect in a strict sense. For example, although several specific color spaces are based on the RGB color model, there is no such thing as the singular RGB color space. == History == In 1802, Thomas Young postulated the existence of three types of photoreceptors (now known as cone cells) in the eye, each of which was sensitive to a particular range of visible light. Hermann von Helmholtz developed the Young–Helmholtz theory further in 1850: that the three types of cone photoreceptors could be classified as short-preferring (blue), middle-preferring (green), and long-preferring (red), according to their response to the wavelengths of light striking the retina. The relative strengths of the signals detected by the three types of cones are interpreted by the brain as a visible color. But it is not clear that they thought of colors as being points in color space. The color-space concept was likely due to Hermann Grassmann, who developed it in two stages. First, he developed the idea of vector space, which allowed the algebraic representation of geometric concepts in n-dimensional space. Fearnley-Sander (1979) describes Grassmann's foundation of linear algebra as follows: The definition of a linear space (vector space)... became widely known around 1920, when Hermann Weyl and others published formal definitions. In fact, such a definition had been given thirty years previously by Peano, who was thoroughly acquainted with Grassmann's mathematical work. Grassmann did not put down a formal definition—the language was not available—but there is no doubt that he had the concept. With this conceptual background, in 1853, Grassmann published a theory of how colors mix; it and its three color laws are still taught, as Grassmann's law. As noted first by Grassmann... the light set has the structure of a cone in the infinite-dimensional linear space. As a result, a quotient set (with respect to metamerism) of the light cone inherits the conical structure, which allows color to be represented as a convex cone in the 3- D linear space, which is referred to as the color cone. == Examples == Colors can be created in printing with color spaces based on the CMYK color model, using the subtractive primary colors of pigment (cyan, magenta, yellow, and key [black]). To create a three-dimensional representation of a given color space, we can assign the amount of magenta color to the representation's X axis, the amount of cyan to its Y axis, and the amount of yellow to its Z axis. The resulting 3-D space provides a unique position for every possible color that can be created by combining those three pigments. Colors can be created on computer monitors with color spaces based on the RGB color model, using the additive primary colors (red, green, and blue). A three-dimensional representation would assign each of the three colors to the X, Y, and Z axes. Colors generated on a given monitor will be limited by the reproduction medium, such as the phosphor (in a CRT monitor) or filters and backlight (LCD monitor). Another way of creating colors on a monitor is with an HSL or HSV color model, based on hue, saturation, brightness (value/lightness). With such a model, the variables are assigned to cylindrical coordinates. Many color spaces can be represented as three-dimensional values in this manner, but some have more, or fewer dimensions, and some, such as Pantone, cannot be represented in this way at all. == Conversion == Color space conversion is the translation of the representation of a color from one basis to another. This typically occurs in the context of converting an image that is represented in one color space to another color space, the goal being to make the translated image look as similar as possible to the original. == RGB density == The RGB color model is implemented in different ways, depending on the capabilities of the system used. The most common incarnation in general use as of 2021 is the 24-bit implementation, with 8 bits, or 256 discrete levels of color per channel. Any color space based on such a 24-bit RGB model is thus limited to a range of 256×256×256 ≈ 16.7 million colors. Some implementations use 16 bits per component for 48 bits total, resulting in the same gamut with a larger number of distinct colors. This is especially important when working with wide-gamut color spaces (where most of the more common colors are located relatively close together), or when a large number of digital filtering algorithms are used consecutively. The same principle applies for any color space based on the same color model, but implemented at different bit depths. == Lists == CIE 1931 XYZ color space was one of the first attempts to produce a color space based on measurements of human color perception (earlier efforts were by James Clerk Maxwell, König & Dieterici, and Abney at Imperial College) and it is the basis for almost all other color spaces. The CIERGB color space is a linearly-related companion of CIE XYZ. Additional derivatives of CIE XYZ include the CIELUV, CIEUVW, and CIELAB. === Generic === RGB uses additive color mixing, because it describes what kind of light needs to be emitted to produce a given color. RGB stores individual values for red, green and blue. RGBA is RGB with an additional channel, alpha, to indicate transparency. Common color spaces based on the RGB model include sRGB, Adobe RGB, ProPhoto RGB, scRGB, and CIE RGB. CMYK uses subtractive color mixing used in the printing process, because it describes what kind of inks need to be applied so the light reflected from the substrate and through the inks produces a given color. One starts with a white substrate (canvas, page, etc.), and uses ink to subtract color from white to create an image. CMYK stores ink values for cyan, magenta, yellow and black. There are many CMYK color spaces for different sets of inks, substrates, and press characteristics (which change the dot gain or transfer function for each ink and thus change the appearance). YIQ was formerly used in NTSC (North America, Japan and elsewhere) television broadcasts for historical reasons. This system stores a luma value roughly analogous to (and sometimes incorrectly identified as) luminance, along with two chroma values as approximate representations of the relative amounts of blue and red in the color. It is similar to the YUV scheme used in most video capture systems and in PAL (Australia, Europe, except France, which uses SECAM) television, except that the YIQ color space is rotated 33° with respect to the YUV color space and the color axes are swapped. The YDbDr scheme used by SECAM television is rotated in another way. YPbPr is a scaled version of YUV. It is most commonly seen in its digital form, YCbCr, used widely in video and image compression schemes such as MPEG and JPEG. xvYCC is an international digital video color space standard published by the IEC (IEC 61966-2-4). It is based on the ITU BT.601 and BT.709