scientific article; zbMATH DE number 1142314
From MaRDI portal
zbMath0900.68316MaRDI QIDQ4385530
Publication date: 14 May 1998
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Monadic second-order definable graph transductions: a survey, Progress measures, immediate determinacy, and a subset construction for tree automata, Integer weighted automata on infinite words, Deterministic asynchronous automata for infinite traces, Rabin tree automata and finite monoids, On fairness and randomness, Weighted automata and weighted logics with discounting, Using integer programming to verify general safety and liveness properties, Axiomatizing the equational theory of regular tree languages, Weighted automata and weighted logics on infinite words, A power-set construction for reducing Büchi automata to non-determinism degree two, Finite automata and ordinals, Towards a descriptive set theory for domain-like structures, Rational digit systems over finite fields and Christol's theorem, Vertex-minors, monadic second-order logic, and a conjecture by Seese, Automata on linear orderings, On decidability properties of local sentences, Observations on determinization of Büchi automata, Skew and infinitary formal power series, The monadic second-order logic of graphs. X: Linear orderings, An automata-theoretic approach to constraint LTL, Algorithmic uses of the Feferman-Vaught theorem, Using automata theory for characterizing the semantics of terminological cycles, Hyperbolicity of monoids presented by confluent monadic rewriting systems., Fine hierarchy of regular \(\omega\)-languages, Interactive foundations of computing, On translations of temporal logic of actions into monadic second-order logic, Choice functions and well-orderings over the infinite binary tree, Logical description of context-free graph languages, Shuffle on trajectories: Syntactic constraints, Processes with infinite liveness requirements, Sofic tree-shifts, Compositional probabilistic verification through multi-objective model checking, Automata-theoretic decision of timed games, Axiomatising extended computation tree logic, Planning control rules for reactive agents, Fixed point characterization of infinite behavior of finite-state systems, On projective and separable properties, On syntactic congruences for \(\omega\)-languages, Automata for epistemic temporal logic with synchronous communication, Typechecking for XML transformers, Finite automata on timed \(\omega\)-trees, Ambiguity in omega context free languages, A hierarchy of deterministic context-free \(\omega\)-languages., Büchi context-free languages, Computation as an unbounded process, The expressive power of analog recurrent neural networks on infinite input streams, Automata and logics over finitely varying functions, \textit{Once} and \textit{for all}, Finite-state automata in information technologies, Program verification: state of the art, problems, and results. II, Inferring answers to queries, The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability, Validating XML document adaptations via hedge automata transformations, A regular characterization of graph languages definable in monadic second-order logic, Computation in finitary stochastic and quantum processes, On automata on infinite trees, Interval logics and their decision procedures. I: An interval logic, Monadic partition logics and finite automata, A topological property of rational \(\omega\)-languages, The monadic second-order logic of graphs. IX: Machines and their behaviours, An initial semantics for the \(\mu\)-calculus on trees and Rabin's complementation lemma, Logical definability on infinite traces, Topological complexity of locally finite \(\omega\)-languages, Verification of well-formed communicating recursive state machines, Fine hierarchies and m-reducibilities in theoretical computer science, Dynamical systems in categories, Visibly pushdown modular games, Synthesis of deterministic top-down tree transducers from automatic tree relations, Synchronized rational relations of finite and infinite words, Infinite trees and automaton-definable relations over \(\omega\)-words, Infinite hypergraphs. II: Systems of recursive equations, Sooner is safer than later, The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable, Infinite games with finite knowledge gaps, Fragments of first-order logic over infinite words, The Borel hierarchy is infinite in the class of regular sets of trees, \(X\)-automata on \(\omega\)-words, Boundary parametrization of self-affine tiles, Stochastic game logic, Decision problems for Turing machines, Finite automata encoding geometric figures, Expressive power of first-order recurrent neural networks determined by their attractor dynamics, Processes with local and global liveness requirements, Topology on words, Finite acceptance of infinite words, Classifying regular languages by a split game, Semantics and strong sequentiality of priority term rewriting systems, The first-order theory of linear one-step rewriting is undecidable, An algorithmic approach for checking closure properties of temporal logic specifications and \(\omega\)-regular languages, Don't care words with an application to the automata-based approach for real addition, A topological characterization of random sequences, Weighted automata and multi-valued logics over arbitrary bounded lattices, Regular sets over extended tree structures, Set constraints and automata, Dynamic linear time temporal logic, On D0L systems with immigration, Infinite games played on finite graphs, Safety and liveness of \(\omega\)-context-free languages, A theory of timed automata, A Model-Theoretic Description of Tree Adjoining Grammars1 1The research presented in this paper was supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 441, TP A2. The authors wish to thank Jens Michaelis and Stephan Kepser for helpful comments., Ultimately periodic words of rational ω-languages, Asymptotic Subword Complexity, Unifying models, Construction of a Deterministicω-Automaton Using Derivatives, Permissive strategies: from parity games to safety games, Automata Theory and Model Checking, Graph Games and Reactive Synthesis, Symbolic Model Checking in Non-Boolean Domains, Equational and membership constraints for infinite trees, The first-order theory of one-step rewriting is undecidable, Semantics and strong sequentially of priority term rewriting systems, Multi-Valued Reasoning about Reactive Systems, Model Checking Linear-Time Properties of Probabilistic Systems, Infinitary Noetherian constructions I. Infinite words, On the Topological Complexity of Infinitary Rational Relations, Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations, The Wadge-Wagner hierarchy of ω-rational sets, Symbolic model checking for probabilistic processes, Expressive Power of Non-deterministic Evolving Recurrent Neural Networks in Terms of Their Attractor Dynamics, Going Beyond Turing with P Automata: Partial Adult Halting and Regular Observer $$\omega $$-Languages, Reasoning About Strategies, Regularity Equals Monadic Second-Order Definability for Quasi-trees, Fine hierarchy of regular ω-languages, Subword Metrics for Infinite Words, Unnamed Item, Characterizing classes of regular languages using prefix codes of bounded synchronization delay, Monitoring first-order interval logic, A product version of dynamic linear time temporal logic, Automatic presentations of structures, Weighted Automata and Weighted Logics with Discounting, An impossibility result in automata-theoretic reinforcement learning, Towards a grand unification of Büchi complementation constructions, BOCoSy: Small but Powerful Symbolic Output-Feedback Control, Compositional synthesis of control barrier certificates for networks of stochastic systems against \(\omega\)-regular specifications, How We Think of Computing Today, On the continuity set of an Omega rational function, A tableau proof system for a mazurkiewicz trace logic with fixpoints, Unnamed Item, Learning Meets Verification, Unnamed Item, Unnamed Item, Complexity of Topological Properties of Regular ω-Languages, Unnamed Item, Practical Efficient Modular Linear-Time Model-Checking, Keeping track of the latest gossip in a distributed system, A hierarchy of tree-automatic structures, The product of rational languages, Well-Quasi Orders and Hierarchy Theory, New Optimizations and Heuristics for Determinization of Büchi Automata, Behavioural equivalence for infinite systems — Partially decidable!, Fairness and regularity for SCCS processes, Axiomatising extended computation tree logic, The expressive power of clocks, Walther recursion, Unification of concept terms in description logics, Safety and Liveness, Weakness and Strength, and the Underlying Topological Relations, Revising Type-2 Computation and Degrees of Discontinuity, Networks of Processes with Parameterized State Space, Level Two of the Quantifier Alternation Hierarchy over Infinite Words, The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey, Locally finite languages, Unnamed Item, Deciding inclusion of set constants over infinite non-strict data structures, Unnamed Item, Automated Compositional Reasoning of Intuitionistically Closed Regular Properties, Topological properties of omega context-free languages, Wadge hierarchy of omega context-free languages, Automata on infinite trees with counting constraints, Computing the Rabin Index of a Parity Automaton, From LTL to Symbolically Represented Deterministic Automata, Topological properties of a class of cubic Rauzy fractals, Lower Bounds on Witnesses for Nonemptiness of Universal Co-Büchi Automata, On Omega-Languages Defined by Mean-Payoff Conditions, On Verifying Fault Tolerance of Distributed Protocols, On Decision Problems for Probabilistic Büchi Automata, Highly Undecidable Problems For Infinite Computations, Power of Randomization in Automata on Infinite Strings, Boundary dynamics for bireversible and for contracting automaton groups, The complexity of weakly recognizing morphisms, Definability in the Infix Order on Words, On Repetition Languages, On global induction mechanisms in aμ-calculus with explicit approximations, Unnamed Item, The Compositional Method and Regular Reachability, On the Complexity of Branching-Time Logics, Unnamed Item, Decidable call by need computations in term rewriting (extended abstract), Topological Characterisation of Multi-Buffer Simulation, Monitor Logics for Quantitative Monitor Automata, Supervisory Control with Complete Observations, Model Checking Omega-regular Properties for Quantum Markov Chains, Some problems in automata theory which depend on the models of set theory, Tomorrow and All our Yesterdays: MTL Satisfiability over the Integers, Recasting Constraint Automata into Büchi Automata, Unnamed Item, Logical definability on infinite traces, Inferring program specifications in polynomial-time, Diophantine equations, Presburger arithmetic and finite automata, Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages, Logic vs topology on regular \(\omega \)-languages, Alternating good-for-MDPs automata, An algorithmic approach for checking closure properties of Ω-regular languages, Towards automata for branching time and partial order, Two Effective Properties of ω-Rational Functions, Integer Weighted Automata on Infinite Words, The Power-Set Construction for Tree Algebras, On the translation of automata to linear temporal logic, Universal first-order quantification over automata, Refuting learning revisited., On omega context free languages which are Borel sets of infinite rank., Well-quasi-orders and regular \(\omega\)-languages, Closure properties of locally finite \(\omega\)-languages, Winning strategies for infinite games: from large cardinals to computer science extended abstract, Bounded model checking of infinite state systems, Regular sets of infinite message sequence charts, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Alternating two-way AC-tree automata, Model measuring for discrete and hybrid systems, Level two of the quantifier alternation hierarchy over infinite words, Infinitary rewriting: closure operators, equivalences and models, Graded modalities in strategy logic, The Kolmogorov complexity of infinite words, The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems, Local Hausdorff dimension, Infinite fuzzy computations, On control of systems modelled as deterministic Rabin automata, Abstraction-based synthesis for stochastic systems with omega-regular objectives, Decidability and universality of quasiminimal subshifts, McNaughton games and extracting strategies for concurrent programs, Supervisory control of discrete event systems, On the relation between reactive synthesis and supervisory control of non-terminating processes, Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization, Symbolic synthesis of masking fault-tolerant distributed programs, Borel hierarchy and omega context free languages., Unambiguous Büchi automata., Model checking of pushdown systems for projection temporal logic, On temporal logic versus Datalog, A gap property of deterministic tree languages., Expressiveness of propositional projection temporal logic with star, Ambiguity, weakness, and regularity in probabilistic Büchi automata, Query efficient implementation of graphs of bounded clique-width, Some subsets of monadic first-order logic (MFO) used for the specification and synthesis of \(\Sigma\)-automata, Computational capabilities of analog and evolving neural networks over infinite input streams, On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets, Inference of \(\omega\)-languages from prefixes., Past pushdown timed automata and safety verification., LTL is closed under topological closure, An automatic method for the dynamic construction of abstractions of states of a formal model, Topology, monitorable properties and runtime verification, Certifying inexpressibility, Concurrent reachability games, A complete characterization of deterministic regular liveness properties, Beyond \(\omega \)-regular languages: \(\omega T\)-regular expressions and their automata and logic counterparts, Symbolic graphs: Linear solutions to connectivity related problems, Code aware resource management, Compositional reasoning using intervals and time reversal, Answering regular path queries in expressive description logics via alternating tree-automata, Rabin's theorem in the concurrency setting: a conjecture, Tree-shifts of finite type, The stuttering principle revisited, Using the compatibility analysis of logical specifications of automata to solve game problems, Weak Muller acceptance conditions for tree automata, On the \(\omega\)-language expressive power of extended Petri nets, Definability and decidability of binary predicates for time granularity, Classical and effective descriptive complexities of \(\omega \)-powers, Tree regular model checking: a simulation-based approach, Periodic generalized automata over the reals, Set constraints with intersection, An expressively complete linear time temporal logic for Mazurkiewicz traces, Improving parity games in practice, A novel learning algorithm for Büchi automata based on family of DFAs and classification trees, On degrees of ambiguity for Büchi tree automata, Decidability results for metric and layered temporal logics, Logic for \(\omega\)-pushdown automata, \( \omega \)-automata, Automata on finite trees, A language hierarchy and kitchens-type theorem for self-similar groups, Structural measures for games and process control in the branch learning model, Systolic tree \(\omega\)-languages: The operational and the logical view, The recognizability of sets of graphs is a robust property, A comparison of tree transductions defined by monadic second order logic and by attribute grammars, The monadic second-order logic of graphs. VIII: Orientations, Solving string problems on graphs using the labeled direct product, A characterization of Büchi tree automata, Product interval automata, A theory of regular MSC languages, Wreath product and infinite words, Verification of probabilistic systems with faulty communication, How to decide continuity of rational functions on infinite words, Relating word and tree automata, Complexity of weak acceptance conditions in tree automata., Determinization of transducers over finite and infinite words., On infinite transition graphs having a decidable monadic theory, Sequentiality, monadic second-order logic and tree automata., Ordering constraints over feature trees expressed in second-order monadic logic., The monadic theory of morphic infinite words and generalizations, The exact complexity of the infinite Post Correspondence Problem, Uniform strategies, rational relations and jumping automata, Synthesis in presence of dynamic links, A hierarchical and modular control architecture for sequential behaviours, Set constraints and topology, A unified language processing methodology, Finite variability interpretation of monadic logic of order, Efficiency of asynchronous systems, read arcs, and the MUTEX-problem, A second-order formulation of non-termination, Qualitative analysis of gene regulatory networks by temporal logic, An operational and denotational approach to non-context-freeness, Shift-invariant topologies for the Cantor space \(X^{\omega}\)
