Transition graphs and the star-height of regular events

DOI10.1307/MMJ/1028998975zbMATH Open0173.01504OpenAlexW1986058515WikidataQ55885172 ScholiaQ55885172MaRDI QIDQ2531871FDOQ2531871

Authors: L. C. Eggan 

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

zbMATH Keywords

languages, automata, networks

Cited In (56)

• Theoretical computer science: computational complexity
• Hierarchical decompositions and termination analysis for generalized planning
• Games for succinctness of regular expressions
• Self-consistent field theory for loop-containing polymers: a general algorithm for path-determination
• General properties of star height of regular events
• Star height of certain families of regular events
• Jumping finite automata: characterizations and complexity
• On depth in EDTOL languages
• Towards fixed-parameter tractable algorithms for abstract argumentation
• Nonnegative companion matrices and star-height of \(\mathbb{N}\)-rational series
• Stamina: stabilisation monoids in automata theory
• On the algorithmic effectiveness of digraph decompositions and complexity measures
• A neural network which computes the square root
• LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
• Algorithms for determining relative star height and star height
• Inversion height in free fields
• Complexity of node coverage games
• Succinctness of regular expressions with interleaving, intersection and counting
• Distance desert automata and the star height problem
• Concatenation-free languages
• Generic results for concatenation hierarchies
• Short Regular Expressions from Finite Automata: Empirical Results
• Entanglement and the complexity of directed graphs
• LIFO-search on digraphs: a searching game for cycle-rank
• Classifying regular languages by a split game
• Factorization Forests
• Classifying regular events in symbolic logic
• Remark on the star-height-problem
• Provably shorter regular expressions from finite automata
• Digraph width measures in parameterized algorithmics
• On digraph width measures in parameterized algorithmics
• On low tree-depth decompositions
• On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups
• Techniques for establishing star height of regular sets
• Unification and combination of a class of traversal strategies made with pattern matching and fixed-points
• Complexity of semi-stable and stage semantics in argumentation frameworks
• The chop of languages
• Algorithms for determining relative inclusion star height and inclusion star height
• How to compute digraph width measures on directed co-graphs
• The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem
• Characterization and complexity results on jumping finite automata
• The solutions of two star-height problems for regular trees
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Representation theorems on regular languages
• Infinite hierarchy of shuffle expressions over a finite alphabet
• Applicability conditions for plans with loops: computability results and algorithms
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Title not available (Why is that?)
• Automata and rational expressions
• Descriptional complexity of 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
• Substitution expressions
• Federation and navigation in SPARQL 1.1
• Concatenation hierarchies: new bottle, old wine

This page was built for publication: Transition graphs and the star-height of regular events

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2531871)