Alternating finite automata and star-free languages

DOI10.1016/S0304-3975(98)00047-4zbMath0944.68090WikidataQ127724572 ScholiaQ127724572MaRDI QIDQ1575674

Sheng Yu, Kai Salomaa

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite automataalternationlanguage equationsstar-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

Expressiveness and complexity of graph logic ⋮ Expressive Capacity of Concatenation Freeness ⋮ Alternation in two-way finite automata ⋮ Expressive capacity of subregular expressions ⋮ Concatenation-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Succinct representation of regular languages by Boolean automata. II
• Succinct representation of regular languages by Boolean automata
• On communication-bounded synchronized alternating finite automata
• Constructions for alternating finite automata^∗
• Alternation
• ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
• On the power of bounded concurrency I
• On finite monoids having only trivial subgroups
• A Note on Star-Free Events
• Derivatives of Regular Expressions

This page was built for publication: Alternating finite automata and star-free languages