Transition graphs and the star-height of regular events
From MaRDI portal
Publication:2531871
DOI10.1307/mmj/1028998975zbMath0173.01504OpenAlexW1986058515WikidataQ55885172 ScholiaQ55885172MaRDI QIDQ2531871
Publication date: 1963
Published in: Michigan Mathematical Journal (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1307/mmj/1028998975
Related Items (52)
The chop of languages ⋮ On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups ⋮ Distance desert automata and the star height problem ⋮ Stamina: stabilisation monoids in automata theory ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Applicability conditions for plans with loops: computability results and algorithms ⋮ Algorithms for determining relative star height and star height ⋮ Inversion height in free fields ⋮ Techniques for establishing star height of regular sets ⋮ Unification and combination of a class of traversal strategies made with pattern matching and fixed-points ⋮ Entanglement and the complexity of directed graphs ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ Nonnegative companion matrices and star-height of \(\mathbb{N}\)-rational series ⋮ On low tree-depth decompositions ⋮ Remark on the star-height-problem ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Digraph width measures in parameterized algorithmics ⋮ Infinite hierarchy of shuffle expressions over a finite alphabet ⋮ On the algorithmic effectiveness of digraph decompositions and complexity measures ⋮ How to compute digraph width measures on directed co-graphs ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ Complexity of semi-stable and stage semantics in argumentation frameworks ⋮ Classifying regular events in symbolic logic ⋮ Unnamed Item ⋮ Algorithms for determining relative inclusion star height and inclusion star height ⋮ Federation and Navigation in SPARQL 1.1 ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Succinctness of regular expressions with interleaving, intersection and counting ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ A neural network which computes the square root ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ Factorization Forests ⋮ Tight Bounds on the Descriptional Complexity of Regular Expressions ⋮ Short Regular Expressions from Finite Automata: Empirical Results ⋮ Classifying regular languages by a split game ⋮ Generic results for concatenation hierarchies ⋮ The solutions of two star-height problems for regular trees ⋮ Substitution expressions ⋮ General properties of star height of regular events ⋮ Star height of certain families of regular events ⋮ Automata and rational expressions ⋮ Descriptional complexity of regular languages ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ On depth in EDTOL languages ⋮ Representation theorems on regular languages ⋮ On the ratio of growth functions in EDTOL languages ⋮ An application of Cohen's result on star height to the theory of control structures ⋮ Complexity of node coverage games ⋮ Characterization and complexity results on jumping finite automata ⋮ Concatenation-free languages
This page was built for publication: Transition graphs and the star-height of regular events
