Results 1 to 10 of about 942 (259)
Automatic functions, linear time and learning [PDF]
Logical Methods in Computer Science, 2013 The present work determines the exact nature of {\em linear time computable} notions which characterise automatic functions (those whose graphs are recognised by a finite automaton). The paper also determines which type of linear time notions permit full
John Case +3 more
doaj +1 more source
Functional Automata - Formal Languages for Computer Science Students [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 An introductory formal languages course exposes advanced undergraduate and early graduate students to automata theory, grammars, constructive proofs, computability, and decidability. Programming students find these topics to be challenging or, in many cases, overwhelming and on the fringe of Computer Science.
Marco T. Morazán, Rosario Antunez
openaire +4 more sources
Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages [PDF]
Logical Methods in Computer ScienceA characteristic sample for a language $L$ and a learning algorithm $\textbf{L}$ is a finite sample of words $T_L$ labeled by their membership in $L$ such that for any sample $T \supseteq T_L$ consistent with $L$, on input $T$ the learning algorithm ...
Dana Angluin, Dana Fisman
doaj +1 more source
Structural Reductions and Stutter Sensitive Properties [PDF]
Logical Methods in Computer ScienceVerification of properties expressed as $\omega$-regular languages such as LTL can benefit hugely from stutter insensitivity, using a diverse set of reduction strategies.
Emmanuel Paviot-Adet +3 more
doaj +1 more source
Completeness Theorems for Kleene algebra with tests and top [PDF]
Logical Methods in Computer ScienceWe prove two completeness results for Kleene algebra with tests and a top element, with respect to guarded string languages and binary relations. While the equational theories of those two classes of models coincide over the signature of Kleene algebra ...
Damien Pous, Jana Wagemaker
doaj +1 more source
Streamability of nested word transductions [PDF]
Logical Methods in Computer Science, 2019 We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that ...
Emmanuel Filiot +3 more
doaj +1 more source
Regular Separability of One Counter Automata [PDF]
Logical Methods in Computer Science, 2019 The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other.
Wojciech Czerwiński, Sławomir Lasota
doaj +1 more source
VisA: A Tool for Visualizing and Animating Automata and Formal Languages [PDF]
, 1998 The use of multimedia tools in education has gained a lot of interest during the last decade (see, e.g., [1]). Free standing multimedia as well as tutorials distributed via the Internet provide the potential for students to learn on their own, at their own pace, and in their own sequence, whereas textbooks or instructors usually impose a sequence how ...
Markus Holzer 0001, Muriel Quenzer
openaire +2 more sources
Finite-valued Streaming String Transducers [PDF]
TheoretiCSA transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, one-way transducers, it is known since the 80s that finite valuedness entails decidability of the equivalence problem.
Emmanuel Filiot +5 more
doaj +1 more source
Constructing Deterministic Parity Automata from Positive and Negative Examples [PDF]
TheoretiCSWe present a polynomial time algorithm that constructs a deterministic parity automaton (DPA) from a given set of positive and negative ultimately periodic example words. We show that this algorithm is complete for the class of $\omega$-regular languages,
León Bohn, Christof Löding
doaj +1 more source