scientific article; zbMATH DE number 3366846
From MaRDI portal
zbMath0231.94041MaRDI QIDQ5639639
Publication date: 1971
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
Equational theories of tropical semirings, Matrix and matricial iteration theories. I, Matrix and matricial iteration theories. II, Inductive \(^{*}\)-semirings, Operations preserving regular languages, Behavioural differential equations: a coinductive calculus of streams, automata, and power series, Some properties of Ising automata, A denotational semantics for low-level probabilistic programs with nondeterminism, A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\), Factor theory and the unity of opposites, An exercise on the generation of many-valued dynamic logics, Axiomatizing recursion-free, regular monitors, Playing with Conway's problem, THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, Metabolic isotopomer labeling systems. III: Path tracing, Representation of normal bands as semigroups of \(k\)-bi-ideals of a semiring, Conway's work on iteration, Axiomatizing rational power series over natural numbers, Inductive semimodules and the vector modules over them., A congruence on the semiring of normal tropical matrices, Automaton partition logic versus quantum logic, Manipulation of regular expressions using derivatives: an overview, Automaton logic, Nonaxiomatisability of equivalences over finite state processes, Deterministic automata. Simulation, universality and minimality, Critical points for least-squares problems involving certain analytic functions, with applications to sigmoidal nets, Components and acyclicity of graphs. An exercise in combining precision with concision, Greibach normal form for \(\omega\)-algebraic systems and weighted simple \(\omega\)-pushdown automata, On quotients of formal power series, The equational logic of fixed points, A calculational approach to mathematical induction, Completeness of Park induction, Typing theorems of omega algebra, Left omega algebras and regular equations, Weighted simple reset pushdown automata, The multiplicative fragment of the Yanov equational theory, On the equational definition of the least prefixed point., Algebraic rewritings for optimizing regular path queries., Towards a linear algebra of programming, Dijkstra, Floyd and Warshall meet Kleene, Parikh's theorem: a simple and direct automaton construction, Flat extensions of groups and limit varieties of additively idempotent semirings, Relation-algebraic verification of Borůvka's minimum spanning tree algorithm, Dynamic Łukasiewicz logic and dynamic MV-algebras, On effective construction of the greatest solution of language inequality \(XA\subseteq BX\), Matrix Code, Computational power of two stacks with restricted communication, Derivatives of rational expressions and related theorems., Adding pebbles to weighted automata: easy specification \& efficient evaluation, Petri net languages and infinite subsets of \(\mathbb{N}^m\), Theory of átomata, On series-parallel pomset languages: rationality, context-freeness and automata, Nondeterministic syntactic complexity, The variety of Kleene algebras with conversion is not finitely based, Verifying minimum spanning tree algorithms with Stone relation algebras, Unnamed Item, Computational completeness of equations over sets of natural numbers, Computational universes, Commutation with codes, A topological approach to transductions, Language equations, maximality and error-detection, A note on identities of two-dimensional languages, Computing by commuting., Algebraically complete semirings and Greibach normal form, Fuzzy regular languages over finite and infinite words, Some properties of inclusions of multisets and contractive Boolean operators, Distributive laws for the coinductive solution of recursive equations, Simple equations on binary factorial languages, A type checking algorithm for concurrent object protocols, An algebraic framework for minimum spanning tree problems, On the complexity of reasoning in Kleene algebra, Left-handed completeness, Kleene algebra of partial predicates, Invariants and closures in the theory of rewrite systems, Types from Frames as Finite Automata, Automata and rational expressions, Equational theories for automata, Language equations, Finite nondeterministic automata: simulation and minimality, Language preorder as a precongruence, THE VALIDITY OF WEIGHTED AUTOMATA, Unique, guarded fixed points in an additive setting, Nonfinitely based ai-semirings with finitely based semigroup reducts, A family of graded epistemic logics, \(L(A)=L(B)\)? decidability results from complete formal systems, Modal algebra and Petri nets, On axioms for commutative regular equations without addition., Conway's problem for three-word sets., Automata, Boolean matrices, and ultimate periodicity., On equations for union-free regular languages, Regular solutions of language inequalities and well quasi-orders, Semiring Neighbours: An Algebraic Embedding and Extension of Neighbourhood Logic, Infinite executions of lazy and strict computations, Multirelational representation theorems for complete idempotent left semirings., A non-ambiguous decomposition of regular languages and factorizing codes, Characterizing determinacy in Kleene algebras, The commutation of finite sets: A challenging problem, On the fine-structure of regular algebra, Conway and iteration hemirings Part 1, The max-plus algebra of the natural numbers has no finite equational basis, Convolution as a Unifying Concept, Feedback, trace and fixed-point semantics, Non-associative Kleene Algebra and Temporal Logics, Stone Relation Algebras, Linear preservers for matrices over a class of semirings, Some quasi-varieties of iteration theories, Unnamed Item, Construction of a Deterministicω-Automaton Using Derivatives, *-Continuous Kleene $$\omega $$-Algebras, Nonfinite axiomatizability of the equational theory of shuffle, Rewriting regular inequalities, Unnamed Item, Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm, SCHEMA FOR PARALLEL INSERTION AND DELETION: REVISITED, Quantales, observational logic and process semantics, Equational axioms for regular sets, Concurrent Kleene Algebra, Matrix versions of aperiodic $K$-rational identities, Unifying Lazy and Strict Computations, Automated Reasoning in Higher-Order Regular Algebra, Left-Handed Completeness, Relational Representation Theorem for Powerset Quantales, Demonic operators and monotype factors, Newton series, coinductively: a comparative study of composition, Rational and Recognisable Power Series, Weighted Automata and Weighted Logics, Temporal Structures, Three New Algorithms for Regular Language Enumeration, Une remarque sur les systèmes complets d'identités rationnelles, Efficient Program Transformers for Translating LCC to PDL, Exploring an Interface Model for CKA, Solving polynomial fixed point equations, Generating Posets Beyond N, Preorders, Partial Semigroups, and Quantales, Latest News about Demonic Algebra with Domain, Automated Reasoning for Hybrid Systems — Two Case Studies —, Solving Linear Equations in *-continuous Action Lattices, Categorical semantics of a simple differential programming language, Automata and one-dimensional TQFTs with defects, Efficient Enumeration of Regular Languages, On difunctions, The Triple-Pair Construction for Weighted ω-Pushdown Automata, Concurrent NetKAT. Modeling and analyzing stateful, concurrent networks, Unnamed Item, Completeness and the finite model property for Kleene algebra, reconsidered, Enhanced coalgebraic bisimulation, Words-to-Letters Valuations for Language Kleene Algebras with Variable Complements, Two-way representations and weighted automata, A Discrete Geometric Model of Concurrent Program Execution, A note on the iteration of infinite matrices, Unnamed Item, Iteration Semirings, Unnamed Item, On embedding in complete semirings, Une condition impliquant toutes les identités rationnelles, On Kleene algebras, On the Coalgebraic Theory of Kleene Algebra with Tests, Bijective sequential mappings of a free monoid onto another, A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS, MINIMALIZATIONS OF NFA USING THE UNIVERSAL AUTOMATON, On Hadamard Series and Rotating Q-Automata, On Language Decompositions and Primality, A Unifying Kleene Theorem for Weighted Finite Automata, Completeness for Identity-free Kleene Lattices, Assertions and recursions, Coinductive Algorithms for Büchi Automata, Elements of Stream Calculus, The algebra of stream processing functions, Unnamed Item, A UNIQUE DECOMPOSITION THEOREM FOR FACTORIAL LANGUAGES, How expressions can code for automata, Matrix Invariants over Semirings, A Finite Axiomatization of Nondeterministic Regular Expressions, Language Decompositions, Primality, and Trajectory-Based Operations, Multi-tilde Operators and Their Glushkov Automata, The View Selection Problem for Regular Path Queries, Uniformizing Rational Relations for Natural Language Applications Using Weighted Determinization, Unnamed Item, Finite Automata as Time-Inv Linear Systems Observability, Reachability and More, Traced Premonoidal Categories, Some more on the basis finite automaton, Partial Conway and Iteration Semiring-Semimodule Pairs, Unnamed Item, KAT-ML: an interactive theorem prover for Kleene algebra with tests, Suites algébriques, automates et substitutions, Reversible Kleene lattices, On the simplest centralizer of a language, John Horton Conway FRS, On Conjugacy of Languages, An algebraic representation of the fixed-point closure of *-continuous Kleene algebras – A categorical Chomsky–Schützenberger theorem, Clifford Algebras, Spin Groups and Qubit Trees, A Fully Equational Proof of Parikh's Theorem, Varieties and covarieties of languages (extended abstract), Simplifying regular expressions further, Fuzzy terms, The universal fuzzy automaton, On language equations with invertible operations, On total regulators generated by derivation relations, Pair algebras and Galois connections., On syntactic nuclei of rational languages, Transitive closure and related semiring properties via eliminants, A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring, Periodic sets of integers, An algebraic approach to computations with progress, Algorithms for Kleene algebra with converse, Developments in concurrent Kleene algebra, Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths, Efficient enumeration of words in regular languages, Notes on equational theories of relations, Brzozowski hierarchy of \(\omega\)-languages, Normal design algebra, Axiomatizing the equational theory of regular tree languages, On regular trace languages, On the active and full use of memory in right-boundary grammars and push- down automata, On flowchart theories. II: The nondeterministic case, Generalised rely-guarantee concurrency: an algebraic foundation, Monoides et semi-anneaux continus. (Continuous monoids and semirings), Bisimilarity is not finitely based over BPA with interrupt, On the computation of quotients and factors of regular languages, An equational axiomatization for multi-exit iteration, Axiomatizing the identities of binoid languages, The equational theory of pomsets, Nested semantics over finite trees are equationally hard, Physical versus computational complementarity. I, On the existence of prime decompositions, Equational properties of iteration in algebraically complete categories, Free inductive \(K\)-semialgebras, Weighted finite automata over hemirings, Subsequential transducers: a coalgebraic perspective, Path sets in one-sided symbolic dynamics, Hopscotch -- reaching the target hop by hop, On the state complexity of closures and interiors of regular languages with subwords and superwords, Free iterative and iteration \(K\)-semialgebras, Proving language inclusion and equivalence by coinduction, On algebra of languages representable by vertex-labeled graphs, On generalized language equations, Completeness for flat modal fixpoint logics, Analogues of quantum complementarity in the theory of automata, A note on ambiguity in context-free grammars, Axiomatizability of positive algebras of binary relations, Container of (min,+)-linear systems, The equational theory of Kleene lattices, Representation theory of finite semigroups over semirings., Local variable scoping and Kleene algebra with tests, Complete systems of \(\mathcal B\)-rational identities, Hidden protocols: modifying our expectations in an evolving world, Partial derivatives of regular expressions and finite automaton constructions, Rewriting extended regular expressions, Equational properties of Kleene algebras of relations with conversion, Empirical logic of finite automata: Microstatements versus macrostatements, Dynamic algebras: Examples, constructions, applications, On transductions of formal power series over complete semirings, On limits in complete semirings, Universal automata and NFA learning, Characterizations of hemirings in terms of cubic \(h\)-ideals, Models of a \(K\)-rational identity system, Weighted automata with discounting, Rewriting of regular expressions and regular path queries, Decision problems for language equations, Fixing Zeno gaps, Introducing VAUCANSON, A coalgebraic approach to Kleene algebra with tests, Algebraic separation logic, Concurrent Kleene algebra and its foundations, On the complexity of decidable cases of the commutation problem of languages, Is observational congruence on \(\mu \)-expressions axiomatisable in equational Horn logic?, Synchronous Kleene algebra, Algebras for iteration and infinite computations, The set of realizations of a max-plus linear sequence is semi-polyhedral, Characterizations of hemirings by their \(h\)-ideals., Algebraic structures for transitive closure, A simplified proof of Parikh's theorem, Computational complementarity and shift spaces, An algebra of hybrid systems, Regular expression order-sorted unification and matching, A note on an expressiveness hierarchy for multi-exit iteration, Conjugacy of finite biprefix codes, On regularity of context-free languages, On a question of A. Salomaa The equational theory of regular expressions over a singleton alphabet is not finitely based, On rational series and rational languages, Equational weighted tree transformations, Group axioms for iteration, The iterated prisoner's dilemma in societies of deterministic players, Computational complementarity, An application of the matrix representation of transductions, The residue of vector sets with applications to decidability problems in Petri nets, A regularity test for dual bordered OS systems, Wolfram's class IV automata and a good Life, Computation theory of cellular automata, Regular algebra applied to language problems, Kleene under a modal demonic star, Abstract abstract reduction
