Titlebook: Machines, Computations, and Universality; 8th International Co Jérôme Durand-Lose,Sergey Verlan Conference proceedings 2018 Springer Intern

STAT

软膏

Control Mechanisms for Array Grammars on Cayley Grids, on Cayley grids of finitely presented groups is investigated. Using .-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules or activation and blocking of rules the same computational power is obtained as w

食道

A Pleasant Stroll Through the Land of Distributed Machines, Computation, and Universality,puted in a distributed system? The answer to this question depends on the environment in which evolves the considered distributed system, i.e., on the assumptions the system relies on. This environment is very often left implicit and nearly always not formulated in terms of precise underlying requir

Ventilator

不遵守

The Language (and Series) of Hammersley-Type Processes,egular language and the Hammersley tree process yields deterministic context-free (but non-regular) languages. For the Hammersley interval process we show that there are . relevant variants of formal languages. One of them leads to the same language as the ordinary Hammersley tree process. The other

collagenase

Minimizing Rules and Nonterminals in Semi-conditional Grammars: Non-trivial for the Simple Case,ne or by a forbidden string alone and is specified in the rule. The maximum length . (., resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional

eardrum

Minimal Useful Size of Counters for (Real-Time) Multicounter Automata,uage by real-time or one-way multicounter automata is .. The same space is required for two-way multicounter automata, independent of whether they are deterministic, nondeterministic, or alternating, and of whether they work with strong or weak space bounds. On the other hand, for deterministic, non

Extricate

A Framework for (De)composing with Boolean Automata Networks,s a strong tool that can be applied to a wide range of models of computation. In this paper we explore a way of working with BANs which involves adding external inputs to the base model (via modules), and more importantly, a way to link networks together using the above mentioned inputs (via wirings

–LOUS

An Extension of Interval-Valued Computing Equivalent to Red-Green Turing Machines,hey serve as basic data units and are called interval-values. It was established that this system (in its unrestricted version) has computing power equivalent to Turing machines, by a rather simple observation. However, this equivalence involves an infinite number of interval-valued variables. In th

种族被根除

Physical Computation and First-Order Logic,arbitrary system, both physical and unphysical, including quantum computers, Blum-Shub-Smale machines, and infinite time Turing machines. We demonstrate that for finite problems, the computational power of any device describable via a finite first-order theory is equivalent to that of a Turing machi