Algorithms for determining relative star height and star height
From MaRDI portal
Publication:1118420
DOI10.1016/0890-5401(88)90033-8zbMath0668.68081OpenAlexW2151259840WikidataQ56061218 ScholiaQ56061218MaRDI QIDQ1118420
Publication date: 1988
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(88)90033-8
Related Items (43)
Equational theories of tropical semirings ⋮ DECIDABILITY OF THE EQUIVALENCE PROBLEM FOR FINITELY AMBIGUOUS FINANCE AUTOMATA ⋮ The limitedness problem on distance automata: Hashiguchi's method revisited ⋮ Multiheuristic approach to discrete optimization problems ⋮ Periodic sets of integers ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS ⋮ Distance desert automata and the star height problem ⋮ Stamina: stabilisation monoids in automata theory ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Inversion height in free fields ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ Monadic logic programs and functional complexity ⋮ Distance automata having large finite distance or finite ambiguity ⋮ On transformations of formal power series. ⋮ Equivalence, Unambiguity, and Sequentiality of Finitely Ambiguous Max-Plus Tree Automata ⋮ The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata ⋮ The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem ⋮ The product of rational languages ⋮ Polynomial operations and hierarchies of concatenation ⋮ Algorithms for determining relative inclusion star height and inclusion star height ⋮ Weak MSO with the unbounding quantifier ⋮ Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton ⋮ Unnamed Item ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Unnamed Item ⋮ Finite sequentiality of unambiguous max-plus tree automata ⋮ Factorization Forests ⋮ Tight Bounds on the Descriptional Complexity of Regular Expressions ⋮ The closure under division and a characterization of the recognizable $\mathcal {Z}$-subsets ⋮ Classifying regular languages by a split game ⋮ Generic results for concatenation hierarchies ⋮ Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring ⋮ Automata and rational expressions ⋮ Max-plus automata ⋮ Descriptional complexity of regular languages ⋮ New upper bounds to the limitedness of distance automata ⋮ On the power of circular splicing ⋮ Operational union-complexity ⋮ Some properties of recognizable \(\mathcal Z\)-subsets ⋮ Characterization and complexity results on jumping finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- The solutions of two star-height problems for regular trees
- Limitedness theorem on finite automata with distance functions
- Representation theorems on regular languages
- A decision procedure for the order of regular events
- Transition graphs and the star-height of regular events
- General properties of star height of regular events
- Star height of certain families of regular events
- Regular languages of star height one
- Homomorphisms that preserve star height
- The star height of reset-free events and strictly locally testable events
- Roots of Star Events
- The loop complexity of pure-group events
- On a question of Eggan
- Techniques for establishing star height of regular sets
This page was built for publication: Algorithms for determining relative star height and star height
