scientific article; zbMATH DE number 2206109

Publication date: 16 September 2005

Full work available at URL: http://www.sciencedirect.com/science/book/9780125321112

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

bi-infinite words infinite trees finite words

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Combinatorics on words (68R15) Applications of game theory (91A80) Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (only showing first 100 items - show all)

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Regular languages of thin trees ⋮ Closure properties of locally finite \(\omega\)-languages ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ Fuzzy tree automata ⋮ Dynamical directions in numeration ⋮ On the complexity of infinite words generated by countable \(q\)-automata ⋮ Weighted automata and weighted logics with discounting ⋮ Level two of the quantifier alternation hierarchy over infinite words ⋮ The word problem for omega-terms over the Trotter-Weil hierarchy ⋮ AF inverse monoids and the structure of countable MV-algebras ⋮ Prognosis of \(\omega\)-languages for the diagnosis of *-languages: a topological perspective ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ Descriptive set theory, from Cantor to Wadge and beyond ⋮ Infinite games specified by 2-tape automata ⋮ The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ Towards a descriptive set theory for domain-like structures ⋮ Inferring regular languages and \(\omega\)-languages ⋮ Automata on linear orderings ⋮ On decidability properties of local sentences ⋮ Observations on determinization of Büchi automata ⋮ Skew and infinitary formal power series ⋮ Sequentializing cellular automata ⋮ Preservation of normality by unambiguous transducers ⋮ On selective unboundedness of VASS ⋮ Fixed points of endomorphisms over special confluent rewriting systems. ⋮ Sofic tree-shifts ⋮ Topological extension of parity automata ⋮ Bisimulation invariant monadic-second order logic in the finite ⋮ Local rule distributions, language complexity and non-uniform cellular automata ⋮ Hyperspaces of a weightable quasi-metric space: application to models in the theory of computation ⋮ Fuzzy local \(\omega\)-systems ⋮ Path sets in one-sided symbolic dynamics ⋮ Schützenberger and Eilenberg theorems for words on linear orderings ⋮ Recognizable sets of power series over finite fields ⋮ Büchi context-free languages ⋮ On detectability of labeled Petri nets and finite automata ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Learning figures with the Hausdorff metric by fractals -- towards computable binary classification ⋮ The expressive power of analog recurrent neural networks on infinite input streams ⋮ Efficient inclusion testing for simple classes of unambiguous \(\omega \)-automata ⋮ Reasoning about graded strategy quantifiers ⋮ Automated temporal equilibrium analysis: verification and synthesis of multi-player games ⋮ Computational capabilities of analog and evolving neural networks over infinite input streams ⋮ Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank ⋮ Which security policies are enforceable by runtime monitors? A survey ⋮ Fixed points of endomorphisms of trace monoids. ⋮ Three research directions in non-uniform cellular automata ⋮ On \(t\)-extensions of the Hankel determinants of certain automatic sequences ⋮ Certifying inexpressibility ⋮ Normality and automata ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Quantitative model-checking of controlled discrete-time Markov processes ⋮ On complexity functions of infinite words associated with generalized Dyck languages ⋮ The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates ⋮ Regular and context-free nominal traces ⋮ Tree-shifts of finite type ⋮ Fragments of first-order logic over infinite words ⋮ Local temporal logic is expressively complete for cograph dependence alphabets ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ The Hausdorff fuzzy quasi-metric ⋮ Boundary parametrization of self-affine tiles ⋮ Recognisability for algebras of infinite trees ⋮ The isomorphism relation between tree-automatic structures ⋮ Classical and effective descriptive complexities of \(\omega \)-powers ⋮ Decimation and interleaving operations in one-sided symbolic dynamics ⋮ Strategical languages of infinite words ⋮ The stable set of a self-map ⋮ Finite-state independence ⋮ Counting branches in trees using games ⋮ Preservation of normality by non-oblivious group selection ⋮ Detecting fictitious states in a \(\Sigma \)-automaton synthesized from its specification in the language LP ⋮ Powers of rationals modulo 1 and rational base number systems ⋮ Expressive power of first-order recurrent neural networks determined by their attractor dynamics ⋮ Nilpotency and periodic points in non-uniform cellular automata ⋮ Infinite periodic points of endomorphisms over special confluent rewriting systems ⋮ On degrees of ambiguity for Büchi tree automata ⋮ Topology on words ⋮ Does the lit-only restriction make any difference for the \(\sigma \)-game and \(\sigma ^+\)-game? ⋮ Weighted automata and multi-valued logics over arbitrary bounded lattices ⋮ Weak bases and quasi-pseudo-metrization of bispaces ⋮ \( \omega \)-automata ⋮ Automata on infinite trees ⋮ Minimisation of automata ⋮ Varieties ⋮ Wadge-Wagner hierarchies ⋮ Equational theories for automata ⋮ On normality in shifts of finite type ⋮ Gardens of Eden in the game of life ⋮ Boolean algebras of regular languages ⋮ Normality and two-way automata ⋮ A characterization of oblivious message adversaries for which consensus is solvable ⋮ On the Weihrauch degree of the additive Ramsey theorem over the rationals ⋮ An analogue of Cobham's theorem for graph directed iterated function systems ⋮ On labeled birooted tree languages: algebras, automata and logic ⋮ Completeness results for omega-regular algebras ⋮ Omega-rational expressions with bounded synchronization delay ⋮ Shift-invariant topologies for the Cantor space \(X^{\omega}\) ⋮ Games with winning conditions of high Borel complexity

Uses Software

MONA

This page was built for publication: