State-complexity of finite-state devices, state compressibility and incompressibility
- 1 September 1993
- journal article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 26 (3) , 237-269
- https://doi.org/10.1007/bf01371727
Abstract
No abstract availableKeywords
This publication has 25 references indexed in Scilit:
- Partial orders on words, minimal elements of regular languages, and state complexityTheoretical Computer Science, 1993
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizationsJournal of Computer and System Sciences, 1992
- Intersection and union of regular languages and state complexityInformation Processing Letters, 1992
- STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGESInternational Journal of Algebra and Computation, 1991
- Concatenation of inputs in a two-way automatonTheoretical Computer Science, 1989
- Finite automata and unary languagesTheoretical Computer Science, 1986
- AlternationJournal of the ACM, 1981
- On equations for regular languages, finite automata, and sequential networksTheoretical Computer Science, 1980
- AlternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- Quasi-realtime languagesTheory of Computing Systems, 1970