Results 21 to 30 of about 307 (62)

Tree generating context-free grammars and regular tree grammars are equivalent [PDF]

, 2022
We show that it is decidable whether the language generated by a given context-free grammar over a tree alphabet is a tree language. Furthermore, if the answer to this question is “yes”, then we can even effectively construct a regular tree grammar which
Kószó, Dávid
core   +2 more sources

Monoid automata for displacement context-free languages

, 2014
In 2007 Kambites presented an algebraic interpretation of Chomsky-Schutzenberger theorem for context-free languages. We give an interpretation of the corresponding theorem for the class of displacement context-free languages which are equivalent to well ...
A. Sorokin, G. Zetzsche, G. Zetzsche, H. Seki, H. Seki, M. Kambites, M. Kanazawa, M. Nivat, R. Yoshinaka, S. Kepser   +9 more
core   +1 more source

An approach to computing downward closures

, 2015
The downward closure of a word language is the set of all (not necessarily contiguous) subwords of its members. It is well-known that the downward closure of any language is regular.
A Ehrenfeucht, AN Maslov, AV Aho, B Courcelle, H Gruber, H Seki, J Dassow, J Dassow, J Leeuwen van, JE Hopcroft, LH Haines, M Jantzen, P Habermehl, PA Abdulla, R Mayr, RH Gilman, T Hayashi, T Smith   +17 more
core   +1 more source

Structural Drift: The Population Dynamics of Sequential Learning [PDF]

, 2012
We introduce a theory of sequential causal inference in which learners in a chain estimate a structural model from their upstream teacher and then pass samples from the model to their downstream student.
Crutchfield, James P., Whalen, Sean
core   +4 more sources

On the group of a rational maximal bifix code

, 2018
We give necessary and sufficient conditions for the group of a rational maximal bifix code $Z$ to be isomorphic with the $F$-group of $Z\cap F$, when $F$ is recurrent and $Z\cap F$ is rational. The case where $F$ is uniformly recurrent, which is known to
Almeida, Jorge, Costa, Alfredo, Kyriakoglou, Revekka, Perrin, Dominique   +3 more
core   +1 more source

The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications [PDF]

, 2017
The principle goal of computational mechanics is to define pattern and structure so that the organization of complex systems can be detected and quantified.
Crutchfield, James P.
core   +1 more source

Convex Language Semantics for Nondeterministic Probabilistic Automata [PDF]

, 2018
We explore language semantics for automata combining probabilistic and nondeterministic behaviors. We first show that there are precisely two natural semantics for probabilistic automata with nondeterminism.
Hsu, J., Ouaknine, J., Silva, A., van Heerdt, G.   +3 more
core   +3 more sources

Tree Transducers and Formal Methods (Dagstuhl Seminar 13192) [PDF]

, 2013
The aim of this Dagstuhl Seminar was to bring together researchers from various research areas related to the theory and application of tree transducers.
Maneth, Sebastian, Seidl, Helmut
core   +1 more source

Descriptional Complexity of Finite Automata -- Selected Highlights

, 2023
The state complexity, respectively, nondeterministic state complexity of a regular language $L$ is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for $L$.
Salomaa, Arto, Salomaa, Kai, Smith, Taylor J.   +2 more
core  

Real-time Regular Expression Matching

, 2023
This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem, which is the growing complexity of automata exponentially depending on regular expression length. This paper presents a
Bernadotte, Alexandra
core