Results 21 to 30 of about 17,250 (168)
Translation from Classical Two-Way Automata to Pebble Two-Way Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2009 We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata with an additional "pebble" movable along the input tape.
Viliam Geffert, Ľubomíra Ištoňová
doaj +1 more source
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure [PDF]
Logical Methods in Computer Science, 2007 String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure.
Joost Engelfriet, Hendrik Jan Hoogeboom
doaj +1 more source
Determinising Parity Automata [PDF]
, 2014 Parity word automata and their determinisation play an important role in automata and game theory. We discuss a determinisation procedure for nondeterministic parity automata through deterministic Rabin to deterministic parity automata. We prove that the
Schewe, Sven, Varghese, Thomas
core +1 more source
Lipschitz Robustness of Finite-state Transducers [PDF]
, 2014 We investigate the problem of checking if a finite-state transducer is robust to uncertainty in its input. Our notion of robustness is based on the analytic notion of Lipschitz continuity --- a transducer is K-(Lipschitz) robust if the perturbation in ...
Henzinger, Thomas A. +2 more
core +4 more sources
Towards a Uniform Theory of Effectful State Machines
, 2020 Using recent developments in coalgebraic and monad-based semantics, we present a uniform study of various notions of machines, e.g. finite state machines, multi-stack machines, Turing machines, valence automata, and weighted automata.
Goncharov, Sergey +2 more
core +2 more sources
, 2006 This paper presents a general framework for modular synthesis of supervisors for discrete event systems. The approach is based on compositional minimisation, using concepts of process equivalence.
Flordal, Hugo, Malik, Robi
core +3 more sources
ON THE PROBLEM OF LOGIC-AUTOMATIC FORMULAS PERFORMABILITY
Известия высших учебных заведений. Поволжский регион: Физико-математические науки, 2020 Background. In the theory of finite automata, there are a number of ways to define finite automata (finitely automatic functions). There are systems of canonical equations among them, Moore diagrams, information trees, schemes of automatic elements ...
S. S. Marchenkov
doaj +1 more source
Caterpillar dualities and regular languages [PDF]
, 2012 We characterize obstruction sets in caterpillar dualities in terms of regular languages, and give a construction of the dual of a regular family of caterpillars.
Erdős, Péter L. +2 more
core +2 more sources
Which Classes of Origin Graphs Are Generated by Transducers. [PDF]
, 2017 We study various models of transducers equipped with origin information. We consider the semantics of these models as particular graphs, called origin graphs, and we characterise the families of such graphs recognised by streaming string ...
Bojanczyk, M. +3 more
core +2 more sources
, 2013 We show that every regular language defines a unique nondeterministic finite automaton (NFA), which we call "\'atomaton", whose states are the "atoms" of the language, that is, non-empty intersections of complemented or uncomplemented left quotients of ...
Brzozowski, Janusz, Tamm, Hellis
core +2 more sources