Series-parallel languages and the bounded-width property
From MaRDI portal
Publication:1566734
DOI10.1016/S0304-3975(00)00031-1zbMath0939.68042OpenAlexW2045594629MaRDI QIDQ1566734
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00031-1
automatarecognizability\(N\)-free posetsrational expressionsbounded parallel widthfork and joinprocess hierarchyseries-parallel poset languages
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Related Items (36)
Towards a language theory for infinite N-free pomsets. ⋮ Equivalence of regular binoid expressions and regular expressions denoting binoid languages over free binoids ⋮ Concurrent Kleene algebra with tests and branching automata ⋮ An Analytic Propositional Proof System on Graphs ⋮ Two equational theories of partial words ⋮ Axiomatizing the identities of binoid languages ⋮ Posets with interfaces as a model for concurrency ⋮ Generating Posets Beyond N ⋮ Nested-unit Petri nets ⋮ Regular binoid expressions and regular binoid languages. ⋮ Concurrent NetKAT. Modeling and analyzing stateful, concurrent networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multilinear representations of free pros ⋮ On series-parallel pomset languages: rationality, context-freeness and automata ⋮ Learning pomset automata ⋮ Series-parallel languages on scattered and countable posets ⋮ Branching automata with costs -- a way of reflecting parallelism in costs ⋮ Algebraic and graph-theoretic properties of infiniten-posets ⋮ Complementation of Branching Automata for Scattered and Countable N-Free Posets ⋮ Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings ⋮ Kleene Theorems for Product Systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Logic and rational languages of scattered and countable series-parallel posets ⋮ A KLEENE THEOREM FOR BISEMIGROUP AND BINOID LANGUAGES ⋮ Complementation of Branching Automata for Scattered and Countable Series-Parallel Posets ⋮ Pomset Languages of Finite Step Transition Systems ⋮ The recognizability of sets of graphs is a robust property ⋮ Asynchronous cellular automata for pomsets ⋮ Unnamed Item ⋮ Rationality in algebras with a series operation ⋮ Pomset Logic ⋮ A categorical framework for learning generalised tree automata ⋮ Kleene Theorems for Synchronous Products with Matching ⋮ Axiomatizing the subsumption and subword preorders on finite and infinite partial words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Free shuffle algebras in language varieties
- Modeling concurrency with partial orders
- The equational theory of pomsets
- Petri nets, event structures and domains. I
- Concurrent regular expressions and their relationship to Petri nets
- Lectures on Petri nets. 1: Basic models. Advances in Petri nets
- Rationality in algebras with a series operation
- A Reiterman theorem for pseudovarieties of finite first-order structures
- Tree acceptors and some of their applications
- Notes on finite asynchronous automata
- The Recognition of Series Parallel Digraphs
- Algebraic automata and context-free sets
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Asynchronous cellular automata for pomsets without auto-concurrency
This page was built for publication: Series-parallel languages and the bounded-width property